題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2647

?

題意是給你n點m條有向邊，葉子點(出度為0)上的值為888，父親點為888+1，依次計算... 讓你求最小的值，但是中間出現有向環就不行了，輸出-1。

?

拓撲排序隊列實現，因為葉子是最小的，所以把邊反向就可以求了。

//拓撲隊列實現 //就是先把入度為0的先入隊，然后每次出隊的時候把相鄰的點的入度減1，要是入度為0則再入隊，不斷循環直到隊列為空 //時間復雜度為O(N + E) //這題就是把邊反向就好了 #include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <vector> using namespace std; const int MAXN = 1e4 + 5; typedef pair <int , int> P; vector <int> G[MAXN]; int du[MAXN]; int main() {int n , m , u , v;while(~scanf("%d %d" , &n , &m)) {for(int i = 1 ; i <= n ; i++) {G[i].clear();du[i] = 0;}for(int i = 0 ; i < m ; i++) {scanf("%d %d" , &u , &v);G[v].push_back(u);du[u]++;}queue <P> que;while(!que.empty()) {que.pop();}int cont = 0 , res = 0;for(int i = 1 ; i <= n ; i++) {if(!du[i]) {que.push(P(i , 888));res += 888;cont++;}}while(!que.empty()) {P temp = que.front();que.pop();for(int i = 0 ; i < G[temp.first].size() ; i++) {du[G[temp.first][i]]--;if(!du[G[temp.first][i]]) {que.push(P(G[temp.first][i] , temp.second + 1));res += temp.second + 1;cont++;}}}if(cont == n) {cout << res << endl;}else {cout << -1 << endl;}} }

?

轉載于:https://www.cnblogs.com/Recoder/p/5271966.html

總結

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

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