[luoguP1993] 小 K 的农场（差分约束 + spfa 判断负环）

传送门

差分约束系统。。找负环用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

上一篇：[luoguP2387] 魔法森林（LCT + 并查集）

下一篇：[luoguP1403] [AHOI2005]约数研究（这。。。）

---

spfa 负环 差分约束