传送门
差分约束系统。。找负环用spfa就行
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 100001 5 6 int n, m, cnt; 7 int head[N], to[N << 1], val[N << 1], next[N << 1], dis[N]; 8 bool vis[N]; 9 10 inline int read() 11 18 19 inline void add(int x, int y, int z) 20 26 27 inline bool spfa(int u) 28 40 } 41 vis[u] = 0; 42 return 1; 43 } 44 45 int main() 46 } 64 memset(dis, 127 / 3, sizeof(dis)); 65 for(i = 1; i <= n; i++) add(0, i, 0); 66 dis[0] = 0; 67 spfa(0) ? puts("Yes") : puts("No"); 68 return 0; 69 }View Code
上一篇：[POJ1733]Parity game（并查集 + 离散化）
下一篇：[CODEVS1914] 运输问题（最小费用最大流）
负环 spfa 差分约束
