HDU 1285 确定比赛名次(拓扑排序基础)

题目大意：

　　题目是说，给你一个ｎ个节点的有向无环图，然后，对于这个无环图，我们对他进行拓扑排序，使得拓扑排序中的序列按照字典序的方式输出.

解题思路：

　　直接套用toposort()模板。。。

　　先说说toposort()的含义：

　　拓扑排序就是说，我们在一完成一项工程的时候，这个工程分为了很多的子工程，我们不可能每次都一下完成很多的工程，我们要按照一定事

务之间的内在联系来完成相应的工程，比如你要完成A工程，那么你必须先完成B工程，所以说B的优先级高于A。那么我们有建图。。

代码：

 1 # include<cstdio>
 2 # include<iostream>
 3 # include<fstream>
 4 # include<algorithm>
 5 # include<functional>
 6 # include<cstring>
 7 # include<string>
 8 # include<cstdlib>
 9 # include<iomanip>
10 # include<numeric>
11 # include<cctype>
12 # include<cmath>
13 # include<ctime>
14 # include<queue>
15 # include<stack>
16 # include<list>
17 # include<set>
18 # include<map>
19 
20 using namespace std;
21 
22 const double PI=4.0*atan(1.0);
23 
24 typedef long long LL;
25 typedef unsigned long long ULL;
26 
27 # define inf 999999999
28 # define MAX 521
29 
30 int edge[MAX][MAX];//邻接矩阵
31 int index[MAX];
32 int book[MAX];
33 int top;
34 int n,m;
35 
36 
37 void init()
38 {
39     memset(edge,0,sizeof(edge));
40     for ( int i = 1;i <= n;i++ )
41     {
42         index[i] = 0;
43         book[i] = 0;
44     }
45     for ( int i = 0;i < m;i++ )
46     {
47         int t1,t2;
48         scanf("%d %d",&t1,&t2);
49         if ( edge[t1][t2] == 0 )
50         {
51             edge[t1][t2] = 1;
52             index[t2]++;
53         }
54     }
55 }
56 
57 void toposort()
58 {
59     int step;
60     while ( top < n )
61     {
62         for ( int i = 1;i <= n;i++ )
63         {
64             if ( index[i]==0&&book[i]==0 )
65             {
66                 step = i;
67                 break;
68             }
69         }
70         book[step] = 1;
71         if ( top )
72             printf(" ");
73         printf("%d",step);
74 
75         top++;
76         for ( int j = 1;j <= n;j++ )
77         {
78             if ( edge[step][j]==1 )
79             {
80                 index[j]--;
81             }
82         }
83 
84     }
85     printf("
");
86 }
87 
88 int main(void)
89 {
90     while ( scanf("%d %d",&n,&m)!=EOF )
91     {
92         init();
93         top = 0;
94         toposort();
95     }
96     
97     return 0;
98 }

HDU 1285 确定比赛名次(拓扑排序基础)

相关推荐