首页 > 代码库 > CSU 1804: 有向无环图（拓扑排序）

CSU 1804: 有向无环图（拓扑排序）

2024-09-19 05:38:19   215人阅读

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1804

题意：……

思路：对于某条路径，在遍历到某个点的时候，之前遍历过的点都可以到达它，因此在这个时候对答案的贡献就是∑(a1 + a2 + a3 + ... + ai) * bv，其中a是之前遍历到的点，v是当前遍历的点。

这样想之后就很简单了。类似于前缀和，每次遍历到一个v点，就把a[u]加给a[v]，然后像平时的拓扑排序做就行了。

 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 100010 4 typedef long long LL; 5 typedef pair<int, LL> P; 6 const int MOD = 1e9 + 7; 7 struct Edge { 8     int v, nxt; 9 } edge[N];10 int vis[N], n, m, head[N], tot, in[N];11 LL a[N], b[N], ans;12 queue<int> que;13 14 void Add(int u, int v) { edge[tot] = (Edge) { v, head[u] }; head[u] = tot++; }15 16 void BFS() {17     while(!que.empty()) que.pop();18     for(int i = 1; i <= n; i++)19         if(in[i] == 0) que.push(i);20     while(!que.empty()) {21         int u = que.front(); que.pop();22         for(int i = head[u]; ~i; i = edge[i].nxt) {23             int v = edge[i].v;24             ans = (ans + a[u] * b[v] % MOD) % MOD;25             a[v] = (a[u] + a[v]) % MOD;26             --in[v];27             if(in[v] == 0) que.push(v);28         }29     }30 }31 32 int main() {33     while(~scanf("%d%d", &n, &m)) {34         for(int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);35         ans = tot = 0;36         memset(head, -1, sizeof(head));37         memset(in, 0, sizeof(in));38         for(int i = 1; i <= m; i++) {39             int u, v; scanf("%d%d", &u, &v);40             Add(u, v); in[v]++;41         }42         BFS();43         printf("%lld\n", ans % MOD);44     }45     return 0;46 }

 

CSU 1804: 有向无环图（拓扑排序）


联系
我们