碼蹄集OJ-魔法鏈路
MC0364?魔法鏈路
難度：黃金 時間限制：1 秒 占用內存：256 M 收藏 報錯
小碼妹學會了多重施法，也就是同時施放多個法術的能力，然而多重施法中每個最終施放的法術都需要一些前置的法力運轉，這些中間的法力運轉過程被稱為魔法鏈路。
小碼妹的魔法鏈路可以看作一個有向無環圖（DAG），其中的每一個節點都可以看作一次法力運轉，出度為 0 的節點則是一次最終施放的法術（法術也被視為一次法力運轉）。每次法力運轉都有一個魔力值wi?，每次法力運轉都會獲得其前置法力運轉積累的魔力值以增加威力。
由于對多重施法的掌握并不熟練，小碼妹不能很快知道自己進行法力運轉的順序，以及最終施放出的法術的威力，你能幫幫她嗎？
小碼妹喜歡有序的序列，所以她希望施放法力運轉的最終順序是字典序最小的。
格式
輸入格式：第一行包含兩個整數n,m（1≤n≤105,1≤m≤2×105），n表示法力運轉的個數，m表示魔法鏈路的邊數；
第二行包含n個整數，wi?（1≤wi?≤105）表示節點i的魔力值；
接下來m行，每行包含兩個整數ui?,vi?，表示一條ui?到vi?的邊。
輸出格式：輸出包含兩行，第一行包含n個整數，為法力運轉的最終順序。
第二行包含每個最終施放法術的威力，按最終法術節點編號從小到大輸出。
樣例 1
輸入：
5 5
1 2 3 4 5
1 2
1 3
2 4
3 4
3 5輸出：
1 2 3 4 5
11 9備注
樣例說明：
最終施放的法術為 4,5。
施放法術 4 需要法力運轉 2,3，法力運轉 2,3 均會獲得法力運轉 1 的 1 點魔力值，所以施放法術 4 的威力為(1+2)+(1+3)+4=11。
施放法術 5 需要法力運轉 3，法力運轉 3 會獲得法力運轉 1 的 1 點魔力值，所以施放法術 3 的威力為1+3+5=9。
本題相關知識點： 圖論：拓撲排序
代碼：
?
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector <int> G[N];
int val[N],ru[N],chu[N];
int n,m;
int main( )
{priority_queue <int,vector<int>,greater<int>> qp;cin >> n >> m;for(int i = 1 ; i <= n ; i++){cin >> val[i]; }for(int i = 1 ; i <= m ; i++){int u,v;cin >> u >> v;G[u].push_back(v);ru[v]++;chu[u]++;}for(int i = 1 ; i <= n ; i++){if(ru[i] == 0){qp.push(i);}}while(!qp.empty()){int cur = qp.top();qp.pop();cout << cur << " ";for(auto to : G[cur]){val[to] += val[cur];ru[to]--;if(ru[to] == 0){qp.push(to);}}} cout << endl;for(int i = 1 ; i <= n ; i++){if(chu[i] == 0)cout << val[i] << " ";}return 0;
}
