hdu--1285 && 4857 --正向 || 逆向拓扑排序 && 优先队列

头太晕了喝了太多 ..

就想提一点对于拓扑排序的这2题为什么一个是正向一个是逆向

主要是看题目要求因为拓扑排序的结果总是有很多种存在的

一般来说它会让你输出它指定要求的形式的答案

那么如果是按字典序输出就是 greater<int> 情况下的优先队列并且正向

　　如果是尽量使小的数字靠前输出而不是追求字典序可以考虑逆向拓扑逆向输出

但这些都不是唯一的一定要分析好题目

曾经看过一个讲动态规划的word 说拓扑是为DP作准备的似乎有点道理

这两题代码实在太相像了我都嫌丢人了..........

 1 //正向拓扑排序
 2 #include <iostream>
 3 #include <cstring>
 4 #include <vector>
 5 #include <queue>
 6 using namespace std;
 7 
 8 int n;
 9 const int size = 520;
10 vector<int>ve[size];
11 priority_queue<int,vector<int>,greater<int> >q;
12 int in[size];
13 int arr[size];
14 
15 void init( )
16 {
17     for( int i = 0 ; i<size; i++ )
18     {
19         in[i] = 0;
20         ve[i].clear();
21     }
22 }
23 
24 void topo( )
25 {
26     int cnt = 0 , now , u;
27     for( int i = 1 ; i<=n ; i++ )
28     {
29         if( in[i] == 0 )
30         {
31             q.push(i);
32         }
33     }
34     while( !q.empty() )
35     {
36         now = q.top();
37         q.pop();
38         arr[cnt++] = now;
39         for( int i = 0 ; i<ve[now].size() ; i++ )
40         {
41             u = ve[now][i];
42             in[u] --;
43             if( in[u] == 0 )
44             {
45                 q.push(u);
46             }
47         }
48     }
49     for( int i = 0 ; i<cnt-1 ; i++ )
50     {
51         cout << arr[i] << " ";
52     }
53     cout << arr[cnt-1] << endl;
54 }
55 
56 int main()
57 {
58     cin.sync_with_stdio(false);
59     int m , x , y;
60     while( cin >> n >> m )
61     {
62         init();
63         while( m-- )
64         {
65             cin >> x >> y;
66             ve[x].push_back(y);
67             in[y] ++;
68         }
69         topo();
70     }
71     return 0;
72 }

View Code

 1 //逆向拓扑排序
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #include <vector>
 6 using namespace std;
 7 
 8 int n;
 9 const int size = 30010;
10 int in[size];
11 int arr[size];
12 vector<int>ve[size];
13 priority_queue<int,vector<int>,less<int> >q;
14 
15 void init( )
16 {
17     for( int i = 1 ; i<=n ; i++ )
18     {
19         ve[i].clear();
20         in[i] = 0;
21     }
22 }
23 
24 void topo( )
25 {
26     int cnt = 0;
27     for( int i = 1 ; i<=n ; i++ )
28     {
29         if( in[i] == 0 )
30         {
31             q.push(i);
32         }
33     }
34     while( !q.empty() )
35     {
36         int now = q.top();
37         q.pop();
38         arr[cnt++] = now;
39         for( int i = 0 ; i<ve[now].size() ; i++ )
40         {
41             int u = ve[now][i];
42             in[u] --;
43             if( in[u] == 0 )
44             {
45                 q.push(u);
46             }
47         }
48     }
49     for( int i = cnt-1 ; i>=1 ; i-- )
50     {
51         cout << arr[i] << " ";
52     }
53     cout << arr[0] << endl;
54 }
55 
56 int main()
57 {
58     cin.sync_with_stdio(false);
59     int t , m , x , y;
60     cin >> t;
61     while( t-- )
62     {
63         cin >> n >> m;
64         init( );
65         while( m-- )
66         {
67             cin >> x >> y;
68             in[x] ++;
69             ve[y].push_back(x);
70         }
71         topo();
72     }
73     return 0;
74 }

View Code

today:

　　一年之前我喝醉了你陪我去南湖边吹风

　　一年之后我喝醉了我陪他们去ktv .....　　

just follow your heart