教学计划编制问题

发表于 | 浏览 次

LinkQueue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
#define QElemType int

//链队列结点结构
struct LinkNode {
    QElemType data;
    LinkNode *next;
};

//带头结点的链队列结构
struct LinkQueue {
    LinkNode  *front;         //队头指针
    LinkNode  *rear;          //队尾指针
};

//构造一个空的链队列。
void InitQueue( LinkQueue &Q )
{
    Q.front = Q.rear = new LinkNode;
    Q.front->next = NULL;
}//LinkQueue

//将链队列清空。
void ClearQueue( LinkQueue &Q )
{
    LinkNode *p;
    while ( Q.front->next != NULL )
    {
        p = Q.front->next;
        Q.front->next = p->next;
        delete p;
    }
    Q.rear = Q.front;
}

//链队列结构销毁。
LinkQueue DestroyQueue( LinkQueue &Q )
{
    ClearQueue( Q );  //成员函数Clear()的功能是释放链表中的所有元素结点
    delete Q.front;
    Q.front = Q.rear = NULL;
}

//判链队列是否为空，若为空，则返回true，否则返回false。
bool QueueEmpty( LinkQueue Q )
{
    return Q.front == Q.rear;
}

//返回链队列中元素个数。
int QueueLength( LinkQueue Q )
{
    int i = 0;
    LinkNode *p = Q.front->next;
    while ( p != NULL )
    {
        i++;
        p = p->next;
    }
    return i;
}

//取链队列队头元素的值。先决条件是队列不空。
QElemType GetHead( LinkQueue &Q )
{
    return Q.front->next->data;
}

//取链队列队尾元素的值。先决条件是队列不空。
QElemType GetLast( LinkQueue &Q )
{
    return Q.rear->data;
}

//链队列入队，插入e到队尾。
void EnQueue( LinkQueue &Q, QElemType e )
{
    LinkNode *p;
    p = new LinkNode ;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}

//链队列出队。先决条件是队列不空。
bool DeQueue( LinkQueue &Q,QElemType &e )
{
    if ( QueueEmpty( Q ) )
        return false;
    LinkNode *p = Q.front->next;
    Q.front->next = p->next;
    e = p->data;
    if ( p == Q.rear )
	    Q.rear = Q.front;  //若出队后队列为空，需修改Q.rear。
    delete p;
    return true;
}

#endif

教学计划编制问题.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include "stdio.h"
#include "cstring"
#include "stdlib.h"
#include "map"
#include "string"
#include "stack"
#include "LinkQueue.h"
#include "iostream"

using namespace std;
typedef long long ll;

const int MAXN=200;

struct ArcBox{
    int tailvex,headvex;
    ArcBox *hlink,*tlink;
};

struct VexNode{
    ArcBox *firstin,*firstout;
    // int credit;
};
struct Graph{
    VexNode xlist[MAXN];
    int vexnum,arcnum;
}G;

void addedge(int v1,int v2)
{
    ArcBox *p=(ArcBox *)malloc(sizeof(ArcBox));
    *p={v1,v2,G.xlist[v2].firstin,G.xlist[v1].firstout};
    G.xlist[v2].firstin=G.xlist[v1].firstout=p;
}
std::map<string,int> CourseToId;
LinkQueue que[2];
char IdToCourse[MAXN][20];
int in[MAXN];
int list[MAXN];
int credit[MAXN];
bool vis[MAXN];
int main(int argc, char const *argv[]) {
    // freopen("input.txt","r",stdin);
    memset(in,0,sizeof in);
    memset(vis,0,sizeof vis);
    CourseToId.clear();
    for(int i=0;i<2;++i)
        InitQueue(que[i]);
    int index=0;
    int sumcredit=0;

    int numSemaster,creditlim,numCourse,numedge;
    printf("请输入学期数，学分上限，课程数，前置课程限制数\n" );
    scanf("%d%d%d%d",&numSemaster,&creditlim,&numCourse,&numedge);
    G.vexnum=numCourse; G.arcnum=numCourse;
    for(int i=0;i<G.vexnum;i++) G.xlist[i].firstin=NULL,G.xlist[i].firstout=NULL;
    printf("请输入课程名和学分\n" );
    for(int i=0;i<numCourse;++i)
    {
        scanf("%s %d",IdToCourse[i],&credit[i]);
        sumcredit+=credit[i];
        CourseToId[IdToCourse[i]]=i;
    }
    printf("请输入课程的前置课程和该课程\n" );
    for(int i=0;i<numedge;++i)
    {
        char c1[100],c2[100];
        scanf("%s %s",c1,c2);
        int p1=CourseToId[c1];
        int p2=CourseToId[c2];
        addedge(p1,p2);
        in[p2]++;
    }
    ll nin[MAXN],sin[MAXN];
    for(int i=0;i<numCourse;++i) sin[i]=in[i];

    printf("finish all course as fast as possible\n" );
    ll cnt=1;
    int curque=0;
    for(int i=0;i<numCourse;++i)
        if(!in[i]) EnQueue(que[curque],i);
    while(cnt<=numSemaster)
    {
        if(QueueEmpty(que[curque])) break;
        printf("Semaster %I64d: ",cnt);
        // for(ll i=0;i<numCourse;++i) nin[i]=in[i];
        ll curcredit=0;
        // for(int i=0;i<numCourse && curcredit<creditlim;++i)
        while(!QueueEmpty(que[curque]) && curcredit<creditlim)
        {
            int u=GetHead(que[curque]);
            if(curcredit+credit[u]<=creditlim)
            {
                // vis[u]=1;
                int tem;
                DeQueue(que[curque],tem);
                curcredit+=credit[u];
                printf("%s ",IdToCourse[u]);
                for(ArcBox *p=G.xlist[u].firstout;p!=NULL;p=(*p).tlink)
                {
                    int v=(*p).headvex;
                    in[v]--;
                    if(!in[v])
                        EnQueue(que[!curque],v);
                }
            }
        }
        while(!QueueEmpty(que[curque])) {
            int tem;
            DeQueue(que[curque],tem);
            EnQueue(que[!curque],tem);
        }
        curque=!curque;
        puts("");
        cnt++;
    }
    for(int i=0;i<numCourse;++i) in[i]=sin[i];
    // for(int i=0;i<2;++i)
    //     ClearQueue(que[i]);
    curque=0;
    for(int i=0;i<numCourse;++i)
        if(!in[i]) EnQueue(que[curque],i);
    printf("make the credit of each semaster as equivalent as possible\n" );
    double ave=sumcredit/(double)numSemaster;
    cnt=1;
    ll cursumcredit=0;
    while(cnt<=numSemaster)
    {
        if(QueueEmpty(que[curque]))  break;
        printf("Semaster %lld: ",cnt);
        ll curcredit=0;
        while(!QueueEmpty(que[curque]) && curcredit<creditlim)
        {
            // printf("test\n" );
            int u=GetHead(que[curque]);
            if(curcredit+credit[u]<=creditlim && cursumcredit+credit[u]<=ave*cnt)
            {
                // vis[u]=1;
                int tem;
                DeQueue(que[curque],tem);
                curcredit+=credit[u];
                cursumcredit+=credit[u];
                printf("%s ",IdToCourse[u]);
                for(ArcBox *p=G.xlist[u].firstout;p!=NULL;p=(*p).tlink)
                {
                    int v=(*p).headvex;
                    in[v]--;
                    if(!in[v])
                        EnQueue(que[!curque],v);
                }
            }else break;
        }
        while(!QueueEmpty(que[curque])){
            int tem;
            DeQueue(que[curque],tem);
            EnQueue(que[!curque],tem);
        }
        curque=!curque;
        puts("");
        cnt++;
    }
    return 0;
}