传送门
1.开两个并查集 f[x] 表示 x 的同类 f[x + n] 表示 x 的敌人
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define N 200001 4 5 int T, n, m; 6 int f[N]; 7 8 inline int read() 9 16 17 inline int find(int x) 18 21 22 inline void connect(int x, int y) 23 28 29 int main() 30 50 else 51 55 } 56 } 57 }View Code
2.带权并查集
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define N 1000001 4 5 int T, n, m; 6 int f[N], d[N]; 7 8 inline int read() 9 16 17 inline int find(int x) 18 25 return f[x]; 26 } 27 28 inline void connect(int x, int y) 29 34 35 int main() 36 57 } 58 } 59 return 0; 60 }View Code
上一篇：[POJ3728]The merchant（tanrjan_lca + DP）
下一篇：[CODEVS1912] 汽车加油行驶问题（分层图最短路）
并查集
