任务安排

问题 C: 任务安排

时间限制: 1 Sec 内存限制: 128 MB
提交: 91 解决: 5
[状态] [命题人:gyx]

题目描述

作为规划局长的你成功确定了城市C的改造方案，方案共有n个子任务，由于要保证城市的正常运转，所以任务之间无法相互独立进行，某些任务需要在另一些任务完成之后才能进行。

输入

输入第一行包含两个整数n和m，分别表示任务的个数和任务之间具有的依赖关系数量。
以下m行每行包含两个整数i和j，表示任务i完成之后任务j才能开始。

输出

输出一行，包含n个用空格隔开的数字，表示可以完成所有任务的方案顺序，如果有多种方案，按照下列策略输出：
完成前置方案后，优先完成后续方案；
有多个方案可选时，优先完成序号较小的方案。
如果没有可行方案，输出-1。

样例输入

样例输出

1 2 3 4 5

提示

【数据范围】
对于100%的数据，1<=n<=1000。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[1005][1005],n,m,ans[1005],s,b[1005],t[1005];
 4 int main()
 5 {
 6     scanf("%d%d",&n,&m);
 7     for(int i=1;i<=m;i++)
 8     {
 9         int x,y;
10         scanf("%d%d",&x,&y);
11         a[y][++b[y]]=x;
12         t[y]=1;
13     }
14     for(int i=1;i<=n;i++)
15     {
16         if(t[i]==0)
17         {
18             ans[++s]=i;
19             t[i]=-1;
20             for(int j=1;j<=n;j++) 
21             {
22                 if(t[j]!=0&&t[j]!=-1)
23                 {
24                     for(int k=1;k<=b[j];k++)
25                     {
26                         if(a[j][k]==i) 
27                         {
28                             a[j][k]=0;
29                             bool f=false;
30                             for(int lhy=1;lhy<=b[j];lhy++)
31                             {
32                                 if(a[j][lhy]!=0) 
33                                 {
34                                     f=true;
35                                     break;
36                                 }
37                             }
38                             if(f==false) t[j]=0;
39                         }
40                     }
41                 }
42                  
43             }
44             i=0;
45         }
46     }
47     if(s!=n) printf("-1");
48     else
49     {
50         for(int i=1;i<n;i++) printf("%d ",ans[i]);
51         printf("%d",ans[n]);
52     }
53     return 0;
54 }
55 /*
56 5 5
57 1 2 
58 2 3
59 3 4
60 5 4
61 1 5
62 */

View Code