PTA数据结构与算法题目集(中文) 7-34

2022-12-20 16:18:48

PTA数据结构与算法题目集(中文) 7-34

7-34 任务调度的合理性 (25 分)

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

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

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

输入格式:

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

输出格式:

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

输入样例1:

输出样例1:

输入样例2:

输出样例2:

0
题目分析：一道利用拓扑排序的题 考察的是拓扑排序的定义

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<malloc.h>
  5 
  6 typedef struct ENode* Edge;
  7 struct ENode
  8 {
  9     int V1, V2;
 10 };
 11 
 12 typedef struct GNode* Graph;
 13 struct GNode
 14 {
 15     int G[110][110];
 16     int Nv;
 17     int Ne;
 18 };
 19 
 20 int IsEdge(Graph Gra, int V1, int V2)
 21 {
 22     return Gra->G[V1][V2];
 23 }
 24 
 25 void Insert(Graph Gra, Edge E)
 26 {
 27     Gra->G[E->V1][E->V2] = 1;
 28 }
 29 
 30 Graph CreateGraph(int Nv)
 31 {
 32     Graph Gra = (Graph)malloc(sizeof(struct GNode));
 33     Gra->Nv = Nv;
 34     Gra->Ne = 0;
 35     for (int i = 1; i <=Gra->Nv; i++)
 36         for (int j = 1; j <=Gra->Nv; j++)
 37             Gra->G[i][j] = 0;
 38     return Gra;
 39 }
 40 
 41 int Queue[110];
 42 int Rear = 0;
 43 int Front = 1;
 44 int Size = 0;
 45 int Succ(int Num)
 46 {
 47     if (Num == 110)
 48         return 0;
 49     else
 50         return Num;
 51 }
 52 
 53 int IsEmpty()
 54 {
 55     return Size == 0;
 56 }
 57 
 58 void EnQueue(int Num)
 59 {
 60     Rear = Succ(Rear + 1);
 61     Queue[Rear] = Num;
 62     Size++;
 63 }
 64 
 65 int DeQueue()
 66 {
 67     int Num = Queue[Front];
 68     Front = Succ(Front + 1);
 69     Size--;
 70     return Num;
 71 }
 72 
 73 int InDegree[110];
 74 int Collected[110];
 75 int Judget(Graph Gra)
 76 {
 77     for (int i = 1; i <=Gra->Nv; i++)
 78         for (int j = 1; j <=Gra->Nv; j++)
 79             if (IsEdge(Gra, i, j))
 80                 InDegree[j]++;
 81     for(int i=1;i<=Gra->Nv;i++)
 82         if (!InDegree[i])
 83         {
 84             EnQueue(i);
 85             Collected[i] = 1;
 86         }
 87     while (!IsEmpty())
 88     {
 89         int V = DeQueue();
 90         for(int i=1;i<=Gra->Nv;i++)
 91             if(!Collected[i]&&IsEdge(Gra,V,i))
 92                 if (--InDegree[i] == 0)
 93                 {
 94                     EnQueue(i);
 95                     Collected[i] = 1;
 96                 }
 97     }
 98     for (int i = 1; i <= Gra->Nv; i++)
 99         if (!Collected[i])
100             return 0;
101     return 1;
102 }
103 int main()
104 {
105     int N;
106     scanf("%d", &N);
107     Graph Gra = CreateGraph(N);
108     Edge E = (Edge)malloc(sizeof(struct ENode));
109     for (int i = 1; i <=N; i++)
110     {
111         E->V2 = i;
112         int n;
113         scanf("%d", &n);
114         for (int j = 0; j < n; j++)
115         {
116             scanf("%d", &(E->V1));
117             Insert(Gra, E);
118         }
119     }
120     if (Judget(Gra))
121         printf("1");
122     else
123         printf("0");
124     return 0;
125 }

View Code

码农公寓