MC0364魔法链路

码蹄集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;
}