題目鏈接【https://vjudge.net/problem/CSU-1804】

題意： 給出一個有向無環圖，然后讓你算下面的結果，count（i，j）表示i->j之間的路徑條數。

題解： 根據公式，可以把SUMa[i]提出來，然后對于沒給我i點求SUMcount(i,j)*bj;

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod = 1e9 + 7; const int maxn = 1e5 + 15; int N, M; LL A[maxn], B[maxn], dp[maxn]; int vis[maxn]; struct Edge {int to, next;Edge (int to = 0, int next = 0): to(to), next(next) {} } E[maxn]; int head[maxn], tot; void initedge() {for(int i = 0; i <= N; i++) head[i] = dp[i] = -1, vis[i] = 0;tot = 0; } void addedge(int u, int v) {E[tot] = Edge(v, head[u]);head[u] = tot++; } LL DFS(int u) {if(dp[u] != -1) return dp[u];vis[u] = 1;dp[u] = 0;for(int k = head[u]; ~k; k = E[k].next){int v = E[k].to;dp[u] = (dp[u] + (B[v] + DFS(v)) % mod) % mod;}return dp[u]; } int main () {while(~scanf("%d %d", &N, &M)){for(int i = 1; i <= N; i++)scanf("%lld %lld", &A[i], &B[i]);initedge();for(int i = 1; i <= M; i++){int u, v;scanf("%d %d", &u, &v);addedge(u, v);}for(int i = 1; i <= N; i++)if(!vis[i]) DFS(i);LL ans = 0;for(int i = 1; i <= N; i++)ans = (ans + (dp[i] * A[i]) % mod) % mod;printf("%lld\n", ans);}return 0; }

?

轉載于:https://www.cnblogs.com/pealicx/p/6994994.html

總結

以上是生活随笔為你收集整理的2016 湖南省省赛B题《有向无环图》的全部內容，希望文章能夠幫你解決所遇到的問題。

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