L3-2 任务调度的合理性

L3-2 任务调度的合理性   (30分)

假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。

但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。

输入格式:

输入说明：输入第一行给出子任务数$N$（$\le 100$），子任务按1~$N$编号。随后$N$行，每行给出一个子任务的依赖集合：首先给出依赖集合中的子任务数$K$，随后给出$K$个子任务编号，整数之间都用空格分隔。

输出格式:

如果方案可行，则输出1，否则输出0。

输入样例1:

12 0 0 2 1 2 0 1 4 1 5 2 3 6 1 3 2 7 8 1 7 1 10 1 7

输出样例1:

1

输入样例2:

5 1 4 2 1 4 2 2 5 1 3 0

输出样例2:

0

/*关键在于找到c[i][j]的代表意思*/

代码如下：

#include<iostream> #include<cstring> using namespace std; int c[110][110],vis[110],a[110],n; int main(){ cin>>n; memset(vis,0,sizeof(vis)); memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); int i,j,k,x; for(i=1;i<=n;i++){ //i号任务 cin>>k; //i号任务的前任务个数 for(j=1;j<=k;j++){ cin>>x; //x是i的前任务 c[x][i]=1; //这里是重点，等于1表示i是 x 的后任务，x 完成后，i 可以释放一个前任务 a[i]++; //i 的前任务个数 } } int num; do{ num=0; for(i=1;i<=n;i++){ if(a[i]==0 && !vis[i]){ //表示i节点前任务个数为0；且还没有释放过它的子任务 vis[i]=1; //开始释放 for(j=1;j<=n;j++){ if(c[i][j]==1){ //i 是 j 的前任务 a[j]--; //释放一个 j 的前任务数量 c[i][j]=0; if(a[j]==0){ num++; //如果释放之后j 的前任务为0，则代表有新的可释放点 } } } } } }while(num!=0); //有新的释放点就再次循环释放 for(i=1;i<=n;i++){ if(a[i]>0){ //当释放完全后，还有任务没完成，代表这个项目不可完成 cout<<"0"<<endl; return 0; } } cout<<"1"<<endl; return 0; }