[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）

传送门

题意

N个点M条边的有向图

每个点有点权

从某一个结点出发

问能获得的最大点权和

一个点的点权最多被计算一次

N<=500000 M<=500000

思路

先tarjan缩点，然后就形成一个dag，无环，所以直接spfa求最长路就行。

也可以先缩点，然后拓扑排序 + dp 搞。

代码

1 #include <map> 2 #include <queue> 3 #include <stack> 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 8 const int MAXN = 500001; 9 int n, m, s, p, cnt, cnt1, tim, sz, ans; 10 int head[MAXN], to[MAXN], next[MAXN], head1[MAXN], to1[MAXN], next1[MAXN]; 11 int a[MAXN], dfn[MAXN], low[MAXN], belong[MAXN], val[MAXN], dis[MAXN]; 12 bool ins[MAXN], vis[MAXN]; 13 std::map <int, int> map1[MAXN]; 14 std::stack <int> S; 15 std::queue <int> q; 16 17 inline int max(int x, int y) 18 21 22 inline int min(int x, int y) 23 26 27 inline int read() 28 35 36 inline void add(int x, int y) 37 42 43 inline void add1(int x, int y) 44 49 50 inline void dfs(int u) 51 64 else if(ins[v]) low[u] = min(low[u], dfn[v]); 65 } 66 if(!(low[u] ^ dfn[u])) 67 76 while(u ^ v); 77 } 78 } 79 80 inline void spfa() 81 102 } 103 } 104 } 105 } 106 107 int main() 108 120 for(i = 1; i <= n; i++) a[i] = read(); 121 s = read(); 122 p = read(); 123 dfs(s); 124 for(i = 1; i <= n; i++) val[belong[i]] += a[i]; 125 for(u = 1; u <= n; u++) 126 for(i = head[u]; i ^ 1; i = next[i]) 127 132 spfa(); 133 for(i = 1; i <= p; i++) 134 138 printf("%d\n", ans); 139 return 0; 140 }
View Code

上一篇：[luoguP1972] [SDOI2009]HH的项链（莫队 || 树状数组 || 主席树）

下一篇：[luoguP3390]【模板】矩阵快速幂

---

stl DP spfa dfs 最短路 tarjan SCC 拓扑排序