首页 > ACM题库 > HDU-杭电 > hdu 2729 Time to Graduate-拓扑排序-[解题报告]C++
2014
02-14

hdu 2729 Time to Graduate-拓扑排序-[解题报告]C++

Time to Graduate

问题描述 :

A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate. Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall. For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall.
In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue.

输入:

There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered(‘F’=Fall, ‘S’=Spring, ‘B’=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.

输出:

There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 ≤ n ≤ 12, which is the number of courses in this data set and m, 2 ≤ m ≤ 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered(‘F’=Fall, ‘S’=Spring, ‘B’=Both semesters), the number of prerequisite courses, p, 0 ≤ p ≤ 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.

样例输入:

4 6
cs123 mt42 cs456 cs789
mt42 F 0
cs123 S 0
cs456 S 2 cs123 mt42
cs789 B 1 cs456
3 6
math1 comp2 comp3
comp3 S 1 comp2
math1 S 0
comp2 F 1 math1
4 3
m10 m20 c33 c44
m10 B 0
m20 B 0
c33 B 0
c44 B 0
-1 -1

样例输出:

The minimum number of semesters required to graduate is 5.
The minimum number of semesters required to graduate is 4.
The minimum number of semesters required to graduate is 2.

 

本题传说暴力就能过的……可是偶RP低,暴怕了……
假如没有m这个限制,那就是简单的拓扑排序。
可惜现在多了个m,所以每次选择的不同就会导致结果的不同。
考虑数据量很小,所以想到状态压缩。用st记录当前的状态(哪些课被修过了)。
如果没有FSB的限制的话,就可以广搜了。
可惜现在又多了个FSB的限制……(汗!)
所以只好做优先队列广搜,因为一个状态可以扩展出两个学期~~~
这样把代码堆积出来就可以啦!
其中一个有用的贪心性质,就是每次扩展尽量多的课。我的处理是专门写了个DFS用于枚举……
然后就1A啦~~~
核心代码:
void dfs(const int &s,const int &dep,const int &id,const int &mdep)
{
if (dep==mdep)
{
if (dps[s]<0)
qs[tl++]=s;
return;
}
if (id>=cdn||cdn-id<mdep-dep) return;
dfs(s|(1<<cds[id]),dep+1,id+1,mdep);
dfs(s,dep,id+1,mdep);
}

inline bool judge(const int &tp,const int &now)
{
if (now&1) return tp<1;
return tp>-1;
}

int bfs()
{
memset(dps,-1,sizeof(dps));
int t=(1<<n)-1;
priority_queue<elem> qu;
qu.push(elem(0,0));
int st,i,j;
bool flag;
elem tmp;
while (dps[t]<0&&!qu.empty())
{
tmp=qu.top();
st=tmp.st;
qu.pop();
if (dps[st]<0)
{
dps[st]=tmp.dep;
cdn=0;
for (i=0;i<n;++i) if ((!(st&(1<<i)))&&judge(tp[i],dps[st]+1))
{
flag=1;
for (j=0;j<adj[i].size()&&flag;++j)
if (!(st&(1<<adj[i][j]))) flag=0;
if (flag) cds[cdn++]=i;
}
tl=0;
if (cdn) dfs(st,0,0,smin(cdn,m));
for (i=0;i<tl;++i)
qu.push(elem(qs[i],dps[st]+1));
cdn=0;
for (i=0;i<n;++i) if ((!(st&(1<<i)))&&judge(tp[i],dps[st]+2))
{
flag=1;
for (j=0;j<adj[i].size()&&flag;++j)
if (!(st&(1<<adj[i][j]))) flag=0;
if (flag) cds[cdn++]=i;
}
tl=0;
if (cdn) dfs(st,0,0,smin(cdn,m));
for (i=0;i<tl;++i)
qu.push(elem(qs[i],dps[st]+2));
}
}
return dps[t];
}

P.S.我的核心代码一般就是把读入和简单的预处理去掉啦,某些人不要老是那么懒,老想要完整的代码,那样不利于思考啊~~~

解题转自:http://hi.baidu.com/accplaystation/item/50bd3b2fb293169ab73263e6


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?