传送门
题意
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的项链（莫队 || 树状数组 || 主席树）
下一篇：[luoguP2858] [USACO06FEB]奶牛零食Treats for the Cows（DP）
DP 最短路 dfs spfa stl tarjan 拓扑排序 SCC
