题目描述
Bobo 有一个 n 个点，m 条边的 有向无环图 （即对于任意点 v，不存在从点 v 开始、点 v 结束的路径）。
为了方便，点用 1 , 2 , … , n编号。
设count(x,y) 表示点 x 到点 y 不同的路径数量（规定count(x,x)=0，Bobo 想知道
∑i=1n∑j=1ncount(i,j)⋅ai⋅bj
除以( 1 0 9 + 7 ) 的余数。
其中，a i , b j 是给定的数列。
输入描述:
输入包含不超过 15 组数据。
每组数据的第一行包含两个整数 n, m (1 ≤ n , m ≤ 105
接下来 n 行的第 i 行包含两个整数 a i , b i
(0≤ai,bi≤109 ).
最后 m 行的第 i 行包含两个整数 ui , vi ，代表一条从点 ui 到 vi 的边(1≤ui,vi≤n)
输出描述:
对于每组数据，输出一个整数表示要求的值。
示例1
输入
3 3 1 1 1 1 1 1 1 2 1 3 2 3
输出
4
示例2
输入
2 2 1 0 0 2 1 2 1 2
输出
4
示例3
输入
2 1 500000000 0 0 500000000 1 2
输出
250000014
因为是DAG图，重要的是不存在环，所以说这道题我们可以通过 拓扑排序 来操作，在拓扑排序的过程中，先将队列里将要pop()的元素u 加上a[u]，然后再从遍历所连边的时候，考虑贡献变化，然后用res记录
#define Clear(x,val) memset(x,val,sizeof x) struct node { int u,v,nex; }e[maxn]; int n,m; int cnt,head[maxn]; ll a[maxn],b[maxn]; int deg[maxn]; ll ans[maxn]; void init() { cnt = 0; Clear(head,-1); Clear(ans,0); Clear(deg,0); } void add(int u,int v){ e[cnt].u = u; e[cnt].v = v; e[cnt].nex = head[u]; head[u] = cnt ++; } ll res; void topoSort(){ queue<int> que; for(int i=1;i<=n;i++){ if(deg[i] == 0) que.push(i); } while(que.size()){ int u = que.front(); que.pop(); ans[u] = (ans[u] + a[u]) % mod; for(int i = head[u];~i;i = e[i].nex){ int to = e[i].v; ans[to] = (ans[to] + ans[u]) % mod; res += ans[u] * b[to]; res %= mod; -- deg[to]; if(deg[to] == 0) que.push(to); } } } int main() { while(cin >> n >> m) { init(); for(int i = 1;i <= n;i ++){ a[i] = read,b[i] = read; } for(int i = 1;i <= m;i ++){ int u = read,v = read; add(u,v); deg[v] ++; } res = 0; topoSort(); cout << res << endl; } return 0; } /** **/
