題意：每個人的工資至少888，然后有m個條件，前者比后者要多。求最少工資。

分析：

最開始的開鄰接矩陣的肯定超時，如果dfs，會出現由于剛開始不是從入度為0的點出發，后期修改不了。比較麻煩。

正確方式是，用隊列實現，不需要像普通隊列一樣，用vis數組標記，而是根據入度是否為0的標準加入隊列。

1 /* 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int maxn = 10000+5; 7 int n,m; 8 9 vector<int> G[maxn]; 10 11 int c[maxn]; 12 int d[maxn]; 13 bool dfs(int u,int k) { 14 c[u] = -1; 15 //d[u] = k; 16 for(int i=0;i<G[u].size();i++) { 17 int v = G[u][i]; 18 19 if(c[v]<0) return false; 20 else if(!c[v]&&!dfs(v,k+1)) return false; 21 22 } 23 24 c[u] = 1; 25 return true; 26 27 } 28 29 bool toposort() { 30 memset(c,0,sizeof(c)); 31 for(int u=1;u<=n;u++) { 32 if(!c[u]) 33 if(!dfs(u,0)) 34 return false; 35 } 36 return true; 37 } 38 39 int main() 40 { 41 freopen("in.txt","r",stdin); 42 while(scanf("%d%d",&n,&m)!=EOF) { 43 44 for(int i=0;i<=n;i++) 45 G[i].clear(); 46 47 for(int i=0;i<m;i++) { 48 int u,v; 49 scanf("%d%d",&u,&v); 50 G[v].push_back(u); 51 } 52 53 memset(d,0,sizeof(d)); 54 55 int sum = 0; 56 57 58 if(toposort()) { 59 for(int i=1;i<=n;i++) { 60 sum+=d[i]; 61 } 62 printf("%d\n",888*n+sum); 63 } 64 else puts("-1"); 65 66 67 } 68 return 0; 69 } 70 */ 71 72 73 #include <bits/stdc++.h> 74 75 using namespace std; 76 77 const int maxn = 10000+10; 78 79 vector<int> G[maxn]; 80 int degree[maxn]; 81 82 83 int main() 84 { 85 //freopen("in.txt","r",stdin); 86 int n,m; 87 while(scanf("%d%d",&n,&m)!=EOF) { 88 89 for(int i=1;i<=n;i++) { 90 G[i].clear(); 91 } 92 memset(degree,0,sizeof(degree)); 93 94 for(int i=0;i<m;i++) { 95 int u,v; 96 scanf("%d%d",&u,&v); 97 G[v].push_back(u); 98 degree[u]++; 99 } 100 101 queue<pair<int,int> > Q; 102 103 int cnt = 0,ans = 0; 104 for(int i=1;i<=n;i++) { 105 if(!degree[i]) { 106 Q.push(make_pair(i,888)); 107 ans+=888; 108 cnt++; 109 } 110 } 111 112 while(!Q.empty()) { 113 pair<int,int> u = Q.front(); 114 Q.pop(); 115 116 for(int i=0;i<G[u.first].size();i++) { 117 int v = G[u.first][i]; 118 degree[v]--; 119 if(!degree[v]) { 120 Q.push(make_pair(v,u.second+1)); 121 ans += u.second + 1; 122 cnt++; 123 } 124 } 125 126 } 127 128 if(cnt==n) 129 printf("%d\n",ans); 130 else puts("-1"); 131 132 133 134 } 135 return 0; 136 } View Code

?

轉載于:https://www.cnblogs.com/TreeDream/p/7214404.html

總結

以上是生活随笔為你收集整理的HDU 2647 拓扑排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。