hdu.5195.DZY Loves Topological Sorting(topo排序 && 贪心） DZY Loves Topological Sorting

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 using namespace std;
 5 const int M = 100005 ;
 6 struct Edge
 7 {
 8     int v , nxt ;
 9     Edge () {}
10     Edge (int v , int nxt) : v (v) , nxt (nxt) {}
11 }e[M];
12 int H[M] , E ;
13 bool vis[M] ;
14 int ans[M] , top ;
15 int in[M] ;
16 int n , m , k ;
17 int u , v ;
18 inline int read () {
19     int ans = 0; char c; bool flag = false;
20     while ((c = getchar()) == ' ' || c == '
' || c == '
');
21     if (c == '-') flag = true; else ans = c - '0';
22     while ((c = getchar()) >= '0' && c <= '9') ans = ans * 10 + c - '0';
23     return ans * (flag ? -1 : 1);
24 }
25 
26 void addedge ()
27 {
28     e[E] = Edge ( v , H[u] ) ;
29     H[u] = E ++ ;
30 }
31 
32 void init ()
33 {
34     E = 0 ;
35     top = 0 ;
36     memset (H , - 1 , sizeof(H)) ;
37     memset (ans , 0 , sizeof(ans) ) ;
38     memset (in , 0 , sizeof(in)) ;
39     memset (vis , 0 , sizeof(vis) ) ;
40 }
41 
42 void topo ()
43 {
44     priority_queue <int> q ;
45     while (!q.empty ()) q.pop () ;
46     for (int i = 1 ; i <= n ; i++) if (in[i] == 0 && !vis[i]) q.push (i) ;
47     while ( !q.empty () ) {
48         int u = q.top () ;
49         q.pop () ;
50         ans[top ++] = u ;
51         for (int i = H[u] ; ~ i ; i = e[i].nxt) {
52             in[e[i].v] -- ;
53             if (in[e[i].v] == 0 && !vis[e[i].v])    q.push (e[i].v) ;
54         }
55     }
56 }
57 
58 void solve ()
59 {
60     init () ;
61     while (m--) {
62         u = read () , v = read () ;
63         addedge () ;
64         in[v] ++ ;
65     }
66     priority_queue <int> q ;
67     for (int i = 1 ; i <= n ; i++)  if (in[i] <= k) q.push (i) ;
68     while ( !q.empty () ) {
69         u = q.top () ;
70         q.pop () ;
71         if (in[u] > k) continue ;
72         ans[top ++] = u ;
73         k -= in[u] ;
74         vis[u] = 1 ;
75         for (int i = H[u] ; ~ i ; i = e[i].nxt) {
76            in[e[i].v] -- ;
77            if (in[e[i].v] <= k && !vis[u] ) q.push (e[i].v) ;
78         }
79     }
80     topo () ;
81     for (int i = 0 ; i < top ; i++) {
82         printf ("%d%c" , ans[i] , i == top - 1 ? '
' : ' ') ;
83     }
84 }
85 
86 int main ()
87 {
88    // freopen ("a.txt" , "r" , stdin ) ;
89     while (~ scanf ("%d%d%d" , &n , &m , &k)) {
90         solve () ;
91     }
92     return 0 ;
93 }