做这套题之前一直以为并查集是很简单的数据结构。
做了才发现自己理解太不深刻。只看重片面的合并集合。。
重要的时发现每个集合的点与这个根的关系，这个关系可以做太多事情了。
题解：
POJ 2236 Wireless Network
10S时限，尽量做到最优吧。一开始还怕会T
预处理出能到达的点。简单题看代码就行了
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 1010; struct point { double x,y; }src[MAXN]; int fa[MAXN]; int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);} bool repair[MAXN]; double dis[MAXN][MAXN]; vector<int>go[MAXN]; int main() { int N; double D; scanf("%d%lf",&N,&D); for (int i = 1 ; i <= N ; i++) scanf("%lf%lf",&src[i].x,&src[i].y); for (int i = 1 ; i <= N ; i++) go[i].clear(); for (int i = 1 ; i <= N ; i++) fa[i] = i; for (int i = 1 ; i <= N ; i++) { for (int j = i + 1 ; j <= N ; j++) { dis[i][j] = sqrt((src[i].x - src[j].x) * (src[i].x - src[j].x) + (src[i].y - src[j].y) * (src[i].y - src[j].y)); dis[j][i] = dis[i][j]; if (dis[i][j] <= D) go[i].push_back(j); if (dis[i][j] <= D) go[j].push_back(i); } } memset(repair,false,sizeof(repair)); char op[5]; while (scanf("%s",op) != EOF) { if(op[0] == 'O') { int x; scanf("%d",&x); repair[x] = true; for (int j = 0 ; j < (int)go[x].size() ; j++) { if (repair[go[x][j]]) { int fx = Find(x); int fy = Find(go[x][j]); if (fx != fy) fa[fx] = fy; } } } else { int x,y; scanf("%d%d",&x,&y); int fx = Find(x); int fy = Find(y); if (fx == fy) puts("SUCCESS"); else puts("FAIL"); } } return 0; }
POJ 1611 The Suspects
有一个学校，有N个学生，编号为0-N-1，现在0号学生感染了非典，凡是和0在一个社团的人就会感染，并且这些人如果还参加了别的社团，他所在的社团照样全部感染，求感染的人数。
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 30010; int fa[MAXN]; int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);} int N,M; int main() { while (scanf("%d%d",&N,&M) != EOF) { if (N == 0 && M == 0) break; for (int i = 0 ; i <= N ; i++) fa[i] = i; for (int i = 0 ; i < M ; i++) { int cnt; scanf("%d",&cnt); int x; scanf("%d",&x); int fx = Find(x); for (int i = 1 ; i < cnt ; i++) { int u; scanf("%d",&u); int fu = Find(u); if (fx != fu) fa[fu] = fx; } } int ret = 1; int need = Find(0); for (int i = 1 ; i < N ; i++) { int fi = Find(i); if (fi == need) ret++; } printf("%d ",ret); } return 0; }
HDU 1213 How Many Tables
有几个集合
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 2010; int fa[MAXN]; int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);} int N,M; bool vis[MAXN]; int main() { int T; scanf("%d",&T); while (T--) { scanf("%d%d",&N,&M); memset(vis,false,sizeof(vis)); for (int i = 0 ; i <= N ; i++) fa[i] = i; while (M--) { int x,y; scanf("%d%d",&x,&y); int fx = Find(x); int fy = Find(y); if (fx != fy) fa[fx] = fy; } int ret = 0; for (int i = 1 ; i <= N ; i++) if (i == Find(i)) ret++; printf("%d ",ret); } return 0; }
HDU 3038 How Many Answers Are Wrong
第一次接触这类题目，一开始完全没想到要用并查集该怎么做，看了别人的代码才慢慢算是理解？
重要的是维护当前点，与当前点和他的跟之间的关系。这道题就变成了到他根的和为多少
我做这道题始终保持跟的下标是其集合内最小的
这道题的路径压缩是很好理解的。
重要的是怎么合并的两颗树。也就是unionset代码。看别人的这个代码困扰了我很久。最后自己手动代入才明白了一些
首先第一保证跟的下标是其集合内最小的 就是代码里要分论讨论的合并fa[x] = y的x和y 的关系
bool unionset(int x,int y,int val)
{
int a = Find(x);
int b = Find(y);
if (a == b)
{
return sum[y] - sum[x] == val;
}
if (a < b)
{
fa[b] = a;
sum[b] = sum[x] + val - sum[y];
}
else
{
fa[a] = b;
sum[a] = sum[y] - val - sum[x];
}
return true;
}
首先sum[x]表示x到他的根的距离
代码中，对于a > b,在数轴上是这情况。1：b--a--x--y 那么fa[a] = b,就要求最左边那段的长度 就是by - xy - ax = ab
对于 a < b 在数轴上是这种情况 2：a--b--x--y 或者3： a--x--b--y 对于第一个情况使得fa[b] = a表示最左边的长度就是ax + xy - by = ab及代码中的sum[b] = sum[x] + val - sum[y];
对于另一种情况 求ab 等于 ax + xy - xy = ab 同样也是那个式子所以可以合并。那么合并集合就可以了
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 200010; int fa[MAXN]; int sum[MAXN]; int Find(int x) { if (x == fa[x]) return x; else { int tmp = fa[x]; fa[x] = Find(fa[x]); sum[x] += sum[tmp]; } return fa[x]; } bool unionset(int x,int y,int val) { int a = Find(x); int b = Find(y); if (a == b) { return sum[y] - sum[x] == val; } if (a < b) { fa[b] = a; sum[b] = sum[x] + val - sum[y]; } else { fa[a] = b; sum[a] = sum[y] - val - sum[x]; } return true; } int main() { int N,M; while (scanf("%d%d",&N,&M) != EOF) { int ret = 0; for (int i = 0 ; i <= N ; i++) fa[i] = i; memset(sum,0,sizeof(sum)); while(M--) { int x,y,val; scanf("%d%d%d",&x,&y,&val); if (!unionset(x - 1,y,val)) ret++; } printf("%d ",ret); } return 0; }
POJ 1182 食物链
这题目是并查集的超经典应用。
说难起始也难，说不难页不难。。！！
首先定义结构体。分别是他的父亲。和他与他这题目是并查集的超经典应用。父亲的关系
relat = 0 表示 其和其父亲是同类
relat = 1 表示 他的父亲吃他
relat = 2 表示 他吃他的父亲
那么初始化就所有值得父亲为他本身，显然他们之间的关系relat = 0本身和本身必然是同类
对于询问假话，如果2个在一个集合里。通过他们和父亲的关系就可以判断他们之间的relat关系来判断假话
第一步 ： 路径压缩如何更新
这个你枚举一下就可以发现儿子和爷爷的relat值=(儿子与父亲的relat值+父亲与爷爷的relat值）%3 举个例子。儿子吃父亲 当前relat = 2，爷爷吃父亲,这个的relat = 1，这种情况
表示儿子和爷爷是同类。所以儿子和爷爷的关系是relat为何只考虑3层，考虑路径压缩压成了几层
第二步 ： 也是我觉得最困扰的如何合并集合。将2个树合并到一起
先给出代码
if (roota != rootb)
{
p[rootb].fa = roota;
p[rootb].relat = (op - 1 + 6 + p[a].relat - p[b].relat) % 3;
}
当前有a->roota ,b -> rootb a和b之间的op值。根据题意有op = 0，表示2者同类，op - 1是我们预先设置的状态值0，op = 2表示a吃b 。根据我们的设置op - 1 = 1表示父亲吃儿子
使得rootb的父亲是roota 那么相关的更新你可以这么看 把这4个点拉成一条链(首先我不知道这么做到底对不对。虽然AC了)
接下来由这张图来看。我们先求rootb和a之间的关系 由前面儿子和爷爷的结论 。我们快速得到这个值等于 （3 - relat[b]) % 3 + (3 - (OP - 1)) % 3
为什么这样注意：relat[b] 表示b和rootb的关系。不是rootb和b的关系。偏移量值需要改变。同理ab也一样。得到这个值后。这里就可以看做b不存在。三层中有roota--a--rootb
再利用这个公式就得到 (（3 - relat[b]) % 3 + (3 - (OP - 1)) % 3 + relat[a]) % 3 合并一下同余一下就得到了上面的合并的式子
最后判断假话
首先其一定在一个集合内。否则其必然是真话，因为遇到不在一个集合里就可以合并集合
第一种判断他们是不是同一类生物。这个直接判断和跟relat即可
另一种判断吃的关系同样也是你手动枚举一下就知道咋弄了。
代码：
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 50010; struct node { int fa; int relat; }p[MAXN]; int Find(int x) { int tmp; if (x == p[x].fa) return x; tmp = p[x].fa; p[x].fa = Find(p[x].fa); p[x].relat = (p[x].relat + p[tmp].relat) % 3; return p[x].fa; } int main() { int N,K; int op; int ret = 0; scanf("%d%d",&N,&K); for (int i = 1 ; i <= N ; i++) { p[i].fa = i; p[i].relat = 0; } for (int i = 1 ; i <= K ; i++) { int a,b; scanf("%d%d%d",&op,&a,&b); if(a > N || b > N) { ret++; continue; } if (op == 2 && a == b) { ret++; continue; } int roota = Find(a); int rootb = Find(b); if (roota != rootb) { p[rootb].fa = roota; p[rootb].relat = (op - 1 + 6 + p[a].relat - p[b].relat) % 3; } else { if(op == 1 && p[a].relat != p[b].relat) { ret++; continue; } if (op == 2 && (3 - p[a].relat + p[b].relat) % 3 != 1) { ret++; } } } printf("%d ",ret); return 0; }
POJ 1417 True Liars
并查集+背包dp
神只说真话，魔鬼直说假话。那就就发现一个很重要的事情！
只要回答yes那么2者同类，否则2者异类。这个不解释了
所以可以用并查集来维护点和根的关系。最后问是否方案数目唯一。于是这个就背包来维护
这个详情看代码吧
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 1010; int fa[MAXN]; int val[MAXN]; bool vis[MAXN]; int Find(int x) { if (x == fa[x]) return x; int tmp = fa[x]; fa[x] = Find(fa[x]); val[x] = (val[x] + val[tmp]) % 2; return fa[x]; } int N,P1,P2; int cnt[MAXN][2]; int dp[MAXN][MAXN]; int pre[MAXN][MAXN]; vector<int>ans; vector<int>res[MAXN][2]; int main() { while(scanf("%d%d%d",&N,&P1,&P2) != EOF) { if (N == 0 && P1 == 0 && P2 == 0) break; for (int i = 0 ; i <= P1 + P2 ; i++) { fa[i] = i; val[i] = 0; } for (int i = 0 ; i < N ; i++) { int x,y; char op[10]; scanf("%d%d%s",&x,&y,op); int fx = Find(x); int fy = Find(y); if (fx != fy) { fa[fy] = fx; int tmp; if (op[0] == 'y') tmp = 0; else tmp = 1; val[fy] = val[x] + val[y] + tmp; } } memset(vis,false,sizeof(vis)); memset(cnt,0,sizeof(cnt)); for(int i = 0 ; i <= P1 + P2 ; i++) { res[i][0].clear(); res[i][1].clear(); } int cas = 1; for (int i = 1 ; i <= P1 + P2 ; i++) { if (vis[i]) continue; int fi = Find(i);//之前写错是因为i这个点不一定是根。我默认这点为跟了。下面就是错误的写法 /* if (vis[i]) continue; vis[i] = true; int fi = Find(i); res[cas][0].push_back(i); cnt[cas][0]++; for (int j = i + 1 ; j <= P1 + P2 ; j++) */ for (int j = i ; j <= P1 + P2 ; j++) { if (vis[j]) continue; int fj = Find(j); if (fj != fi) continue; vis[j] = true; res[cas][val[j]].push_back(j); cnt[cas][val[j]]++; } cas++; } memset(dp,0,sizeof(dp)); cas--; /* for (int i = 1 ; i <= cas ; i++) { for (int j = 0 ; j < (int)res[i][0].size(); j++) printf("%d ",res[i][0][j]); puts(""); for (int j = 0 ; j < (int)res[i][1].size(); j++) printf("%d ",res[i][1][j]); puts(""); printf("%d %d ",cnt[i][0],cnt[i][1]); } */ dp[0][0] = 1; for (int i = 1 ; i <= cas ; i++) { for (int j = P1 ; j >= 0 ; j--) { if (j >= cnt[i][0] && dp[i - 1][j - cnt[i][0]] > 0) { dp[i][j] += dp[i - 1][j - cnt[i][0]]; if (dp[i][j] > 1) dp[i][j] = 2; pre[i][j] = j - cnt[i][0]; } if (j >= cnt[i][1] && dp[i - 1][j - cnt[i][1]] > 0) { dp[i][j] += dp[i - 1][j - cnt[i][1]]; if (dp[i][j] > 1) dp[i][j] = 2; pre[i][j] = j - cnt[i][1]; } } } if (dp[cas][P1] != 1) { puts("no"); continue; } ans.clear(); int cur = P1; for (int i = cas ; i >= 1 ;i--) { int pref = pre[i][cur]; int sub = cur - pref; if (cnt[i][0] == sub) { for (int j = 0 ; j < (int)res[i][0].size(); j++) ans.push_back(res[i][0][j]); } else { for (int j = 0 ; j < (int)res[i][1].size() ; j++) ans.push_back(res[i][1][j]); } cur = pref; } sort(ans.begin(),ans.end()); for (int i = 0 ; i < (int)ans.size() ; i++) printf("%d ",ans[i]); puts("end"); } return 0; }
POJ 1456 Supermarket
这个题数据这么小。怎么做都行。并查集就帮助你理解并查集
首先这是一个贪心
肯定优先选择大的完成。。贪心很明显，因为每个物品只需要执行一天，且全部都是一天
并查集维护点到根之间最近的可用的时间点是什么 ，根下标小与等于树上的点
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 10010; int fa[MAXN]; int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);} struct node { int d,p; friend bool operator < (const node &a,const node &b) { return a.p > b.p; } }src[MAXN]; int N; int main() { while (scanf("%d",&N) != EOF) { for (int i = 0 ; i < N ; i++) scanf("%d%d",&src[i].p,&src[i].d); sort(src,src + N); for (int i = 0 ; i < MAXN ; i++) fa[i] = i; int ret = 0; for (int i = 0 ; i < N ; i++) { int ti = Find(src[i].d); if (ti > 0) { ret += src[i].p; fa[ti] = ti - 1; } } printf("%d ",ret); } return 0; }
POJ 1733 Parity game
同样询问假话在哪
并查集维护点到根之间1的个数是奇数还是偶数。有了前面的铺垫这里就很简单了。
val = 0 儿子到父亲之间为偶数个1，val = 1 儿子到父亲之间为奇数个1
第一：路径压缩 ： 直接儿子val异或父亲val值。
第二：合并集合 ： 直接全异或。
首先我保证 父亲的下标小于儿子。对于a,b之间的一个操作（奇数或者偶数）那么可能的情况是 fb--b--a--fa直接求fa到fb的奇偶性，无论什么情况直接val[b] ^ val[a] ^ ab即可对于其他数轴上的情况
一样的式子
代码：
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 10010; int fa[MAXN],val[MAXN]; map<int,int>mp; int L; int u[MAXN],v[MAXN],ask[MAXN]; // val = 0 even val = 1 odd int Find(int x) { if (x == fa[x]) return x; int tmp = fa[x]; fa[x] = Find(fa[x]); val[x] = val[x] ^ val[tmp]; return fa[x]; } int main() { int N; int cas = 1; while (scanf("%d",&L) != EOF) { mp.clear(); scanf("%d",&N); int ans = N; for (int i = 0 ; i < N ; i++) { scanf("%d%d",&u[i],&v[i]); if (u[i] > v[i]) swap(u[i],v[i]); u[i]--; if (!mp[u[i]]) mp[u[i]] = cas++; if (!mp[v[i]]) mp[v[i]] = cas++; char op[5]; scanf("%s",op); if (op[0] == 'e') ask[i] = 0; else ask[i] = 1; } for (int i = 0 ;i < MAXN ; i++) { fa[i] = i; val[i] = 0; } for (int i = 0 ; i < N ; i++) { int l = mp[u[i]]; int r = mp[v[i]]; int fl = Find(l); int fr = Find(r); if (fl == fr) { if ((val[l] ^ val[r]) != ask[i]) { ans = i; break; } } else { fa[fr] = fl; val[fr] = val[l] ^ val[r] ^ ask[i]; } } printf("%d ",ans); } return 0; }
POJ 1984 Navigation Nightmare
题很难读懂。这个题卡了我好久。我一直看别人代码十分费解。这个向量偏移，相对值到底该怎么理解
真是日了X了
这里都是相对长度，首先只分析南北方向。东西方向一样的分开分析
第一步：路径压缩：儿子相应长度值+=父亲相应长度值
第二部： 合并集合： 就这里我百思不得其解。
下面坐标全部指的是y坐标
首先保证根的坐标在节点坐标的下方。对于向北（上）方向的直线，认为他是正长度，否则为副长度
4个点 ： r1,r2,f1,f2 r1的根为f1,r2的根为f2
则有 f2 到 f1 的长度 + r2 到 f2 的长度 =
r1 到 r2 的长度 + r1 到 f1 的长度 = 向量 r2-f1的长度
东西方向同理
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 40010; int fa[MAXN]; int dx[MAXN],dy[MAXN]; int from[MAXN],to[MAXN],L[MAXN]; char dir[MAXN][5]; struct node { int u,v; int index; int ti; friend bool operator < (const node &a,const node &b) { return a.ti < b.ti; } }src[MAXN]; int ans[MAXN]; int Find(int x) { if (x == fa[x]) return x; int tmp = fa[x]; fa[x] = Find(fa[x]); dy[x] += dy[tmp]; dx[x] += dx[tmp]; return fa[x]; } int main() { int N,M; int Q; while (scanf("%d%d",&N,&M) != EOF) { for(int i = 0 ; i <= N ; i++) fa[i] = i; memset(dx,0,sizeof(dx)); memset(dy,0,sizeof(dy)); for (int i = 1 ; i <= M ; i++) { scanf("%d%d%d",&from[i],&to[i],&L[i]); scanf("%s",dir[i]); } scanf("%d",&Q); for (int i = 0 ; i < Q ; i++) { scanf("%d%d%d",&src[i].u,&src[i].v,&src[i].ti); src[i].index = i; } sort(src,src + Q); int t = 1; for (int i = 0 ; i < Q ; i++) { while (t <= M && src[i].ti >= t) { int f1 = Find(from[t]); int f2 = Find(to[t]); if (f1 != f2) { fa[f2] = f1; if (dir[t][0] == 'N') { dy[f2] = L[t] + dy[from[t]] - dy[to[t]]; dx[f2] = dx[from[t]] - dx[to[t]]; } else if (dir[t][0] == 'S') { dy[f2] = -L[t] + dy[from[t]] - dy[to[t]]; dx[f2] = dx[from[t]] - dx[to[t]]; } else if (dir[t][0] == 'E') { dx[f2] = L[t] + dx[from[t]] - dx[to[t]]; dy[f2] = dy[from[t]] - dy[to[t]]; } else { dx[f2] = -L[t] + dx[from[t]] - dx[to[t]]; dy[f2] = dy[from[t]] - dy[to[t]]; } } t++; } if (Find(src[i].u) != Find(src[i].v)) ans[src[i].index] = -1; else { ans[src[i].index] = abs(dx[src[i].u] - dx[src[i].v]) + abs(dy[src[i].u] - dy[src[i].v]); } } for (int i = 0 ; i < Q ; i++) printf("%d ",ans[i]); } return 0; }
POJ 2492 A Bug's Life
给出交配行为，问是否同性可交配
默认每一次交配为异性，如果有冲突则满足有同性交配
同样和父亲的关系为同性 val值为0，否则为1
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 2010; const int MAXD = 1000010; int fa[MAXN]; int val[MAXN]; int Find(int x) { if (x == fa[x]) return x; int tmp = fa[x]; fa[x] = Find(fa[x]); val[x] = val[x] ^ val[tmp]; return fa[x]; } int main() { // freopen("sample.txt","r",stdin); int T,N,M,kase = 1; bool first = true; scanf("%d",&T); while (T--) { if (first) first = false; else putchar(' '); scanf("%d%d",&N,&M); for (int i = 0 ; i <= N ; i++) { fa[i] = i; val[i] = 0; } bool flag = false; for (int i = 0 ; i < M ; i++) { int u ,v; scanf("%d%d",&u,&v); if (flag) continue; int fu = Find(u); int fv = Find(v); if (fu == fv) { int res = val[u] ^ val[v]; if (res == 0) { flag = true; } } else { fa[fv] = fu; val[fv] = val[u] ^ val[v] ^ 1; } } printf("Scenario #%d: ",kase++); if (flag) puts("Suspicious bugs found!"); else puts("No suspicious bugs found!"); } return 0; }
POJ 2912 Rochambeau
难点是要注意到N很小只有500，那么可以枚举裁判是谁。然后用类似食物链的方法并查集维护处假话。
分情况输出，如果只有一个裁判的情况下。那么分辨出的步数就是不是确定裁判的所有枚举中的最大矛盾round
怎么维护并查集看前面。
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 510; int fa[MAXN]; int val[MAXN]; int Find(int x) { if (x == fa[x]) return x; int tmp = fa[x]; fa[x] = Find(fa[x]); val[x] = (val[x] + val[tmp]) % 3; return fa[x]; } int N,M; struct node { int u,v; int op; }src[4010]; char str[50]; int main() { while (scanf("%d%d",&N,&M) != EOF) { gets(str); for (int i = 0 ; i < M ; i++) { gets(str); int pos; int len = strlen(str); for (pos = 0 ; pos < len ; pos++) if (str[pos] == '=' || str[pos] == '>' || str[pos] == '<') break; int u = 0; for (int j = 0 ; j < pos ; j++) { u = u * 10 + str[j] - '0'; } int v = 0; for (int j = pos + 1 ; j < len ; j++) { v = v * 10 + str[j] - '0'; } src[i].u = u; src[i].v = v; if (str[pos] == '=') src[i].op = 0; else if (str[pos] == '<') src[i].op = 1; else src[i].op = 2; } // for (int i = 0 ; i < M ; i++) // printf("%d %d %d ",src[i].u,src[i].v,src[i].op); int ansi,anst = 0; int cnt = 0; for (int i = 0 ; i < N ; i++) { for (int j = 0 ; j < N ; j++) fa[j] = j; memset(val,0,sizeof(val)); int pos = -1; for (int j = 0 ; j < M ; j++) { if (src[j].u == i || src[j].v == i) continue; int u = src[j].u; int v = src[j].v; int fu = Find(u); int fv = Find(v); if (fu == fv) { if ((3 - src[j].op + val[u]) % 3 != val[v]) { pos = j + 1; break; } } else { fa[fv] = fu; val[fv] = (6 - val[v] - src[j].op + val[u]) % 3; } } if (pos == -1) { cnt++; ansi = i; } else anst = max(anst,pos); } if(cnt == 0)printf("Impossible "); else if(cnt >= 2)printf("Can not determine "); else printf("Player %d can be determined to be the judge after %d lines ",ansi,anst); } return 0; }
ZOJ 3261 Connections in Galaxy War
正向在线做的话有删除操作很难处理，就离线变成从后向前处理变为添加操作
就是普通并查集
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 10010; const int MAXD = 50010; int fa[MAXN]; int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);} int val[MAXN],pos[MAXN]; void unionset(int u,int v) { int fu = Find(u),fv = Find(v); if (fu != fv) { fa[fu] = fv; if (val[fu] > val[fv]) { val[fv] = val[fu]; pos[fv] = pos[fu]; } else if (val[fu] == val[fv] && pos[fu] < pos[fv]) { pos[fv] = pos[fu]; } } } int from[20010],to[20010]; map<int,int>mp[MAXN]; bool vis[20010]; int p[MAXN]; struct node { int op; int u,v; }ask[MAXD]; int ret[MAXD]; int main() { int N; bool first = true; while (scanf("%d",&N) != EOF) { if (first) first = false; else puts(""); for (int i = 0 ; i < N ; i++) { scanf("%d",&p[i]); val[i] = p[i]; pos[i] = i; mp[i].clear(); } for (int i = 0 ; i <= N ; i++) fa[i] = i; int M; scanf("%d",&M); for (int i = 1 ; i <= M ; i++) { scanf("%d%d",&from[i],&to[i]); if (from[i] > to[i]) swap(from[i],to[i]); mp[from[i]][to[i]] = i; vis[i] = false; } int Q; scanf("%d",&Q); for (int i = 0 ; i < Q ; i++) { char op[20]; scanf("%s",op); if(op[0] == 'q') { ask[i].op = 0; scanf("%d",&ask[i].u); } else { ask[i].op = 1; scanf("%d%d",&ask[i].u,&ask[i].v); if (ask[i].u > ask[i].v) swap(ask[i].u,ask[i].v); int tmp = mp[ask[i].u][ask[i].v]; vis[tmp] = true; } } for (int i = 1 ; i <= M ; i++) { if(!vis[i]) unionset(from[i],to[i]); } int tot = 0; for (int i = Q - 1 ; i >= 0 ; i--) { if (ask[i].op == 0) { int fu = Find(ask[i].u); if (val[fu] > p[ask[i].u]) ret[tot++] = pos[fu]; else ret[tot++] = -1; } else { unionset(ask[i].u,ask[i].v); } } tot--; for (int i = tot ; i >= 0 ; i--) printf("%d ",ret[i]); } return 0; }
HDU 1272 小希的迷宫
一个无向图是不是树。注意坑点 第一：森林，第二：空树
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 100010; int fa[MAXN]; int res[MAXN * 10]; int tot; int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);} int main() { // freopen("sample.txt","r",stdin); int u,v; while (scanf("%d%d",&u,&v) != EOF) { if (u == -1 && v == -1) break; if (u == 0 && v == 0) { puts("Yes"); continue; } for (int i = 0 ; i < MAXN ; i++) fa[i] = i; bool flag = false; int fu = Find(u); int fv = Find(v); if (fu != fv) fa[fv] = fu; tot = 0; res[tot++] = u; res[tot++] = v; while (scanf("%d%d",&u,&v) != EOF) { if (u == 0 && v == 0) break; if (flag) continue; int fu = Find(u); int fv = Find(v); res[tot++] = u; res[tot++] = v; if (fu == fv) flag = true; else { fa[fv] = fu; } } sort(res,res + tot); tot = unique(res,res + tot) - res; // for (int i = 0 ; i < tot ; i++) printf("%d ",res[i]); puts(""); int cnt = 0; for (int i = 0 ; i < tot ; i++) { if (Find(res[i]) == res[i]) cnt++; if (cnt >= 2) { flag = true; break; } } if (flag) puts("No"); else puts("Yes"); } return 0; }
POJ 1308 Is It A Tree?
有向图是不是树
连通后仅有一个点的入度为0，其他所有点的入度都为1 即为树
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} const int MAXN = 1000010; int fa[MAXN]; int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);} int deg[MAXN]; bool vis[MAXN]; //这题用并查集判断连通，连通后有且仅有1个入度为0，其余入度为1，就是树了。 //注意树为空的情况。 int main() { int u,v,kase = 1; while (scanf("%d%d",&u,&v) != EOF) { if (u == -1 && v == -1) break; if (u == 0 && v == 0) { printf("Case %d is a tree. ",kase++); continue; } memset(vis,false,sizeof(vis)); vis[u] = vis[v] = true; memset(deg,0,sizeof(deg)); deg[v]++; for (int i = 0 ; i < MAXN ; i++) fa[i] = i; fa[v] = u; while (scanf("%d%d",&u,&v) != EOF) { if (u == 0 && v == 0) break; int fu = Find(u); int fv = Find(v); if (fu != fv) { fa[fv] = fu; } vis[u] = vis[v] = true; deg[v]++; } int num = 0,cnt0 = 0,cnt1 = 0; int pos; bool flag = false; for (int i = 1 ; i < MAXN ; i++) { if (vis[i]) { pos = i; break; } } int need = Find(pos); for (int i = pos ; i < MAXN ; i++) { if (vis[i]) { num++; if (deg[i] == 0) cnt0++; else if (deg[i] == 1) cnt1++; if (Find(i) != need) { flag = true; break; } } } if (cnt0 == 1 && cnt1 + cnt0 == num && !flag) printf("Case %d is a tree. ",kase++); else printf("Case %d is not a tree. ",kase++); } return 0; }