csu1804

題意

給出一個(gè) n 個(gè)點(diǎn)、m 條邊的有向無環(huán)圖。求 \(\sum_{i=1}^{n}\sum_{j=1}^{n}count(i,j)\cdot a_i\cdot b_j\)，\(count(i, j)\) 表示從 i 到 j 不同的路徑數(shù)量。

分析

樹形DP。
dp[i] 表示從 i 點(diǎn)出發(fā)可以到達(dá)的所有子孫的 b 的和。

code

#include<cstdio> #include<cmath> #include<cstring> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 1e5 + 10; const ll MOD = 1e9 + 7; int n, m; ll a[MAXN], b[MAXN]; vector<int> G[MAXN]; ll ans; ll dp[MAXN]; void dfs(int u) {if(dp[u] != -1) return;dp[u] = 0;for(int i = 0; i < G[u].size(); i++) {int v = G[u][i];dfs(v);dp[u] = (dp[u] + dp[v] + b[v]) % MOD;} } int main() {while(~scanf("%d%d", &n, &m)) {for(int i = 1; i <= n; i++) {G[i].clear();scanf("%lld%lld", &a[i], &b[i]);}memset(dp, -1, sizeof dp);for(int i = 0; i < m; i++) {int x, y;scanf("%d%d", &x, &y);G[x].push_back(y);}ans = 0;for(int i = 1; i <= n; i++) {dfs(i);ans = (ans + a[i] * dp[i]) % MOD;}printf("%lld\n", ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ftae/p/7197863.html

總結(jié)

以上是生活随笔為你收集整理的csu1804的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。