之前只知道簡單并查集，做了才學(xué)會了帶權(quán)并查集。感覺很開心。。
D - How Many Answers Are Wrong
帶權(quán)并查集的模板題，不過這題也有需要注意的地方。
1，sum[A]的意義是從A到rootA(rootA<=A)的和，關(guān)鍵點(diǎn)是區(qū)間前開后閉(可以想一想)。
2，由上一點(diǎn)也可以得出，如果想求從A到B的sum，那么需要把A–。
代碼如下:

#include<iostream> #include<stdio.h> #include<cstring> using namespace std; const int maxn = 2e5 + 5; int f[maxn], sum[maxn]; int find(int a) {int pre = f[a];if (a != f[a]){f[a] = find(f[a]);sum[a] += sum[pre];}return f[a]; }int main() {int N, M;while (~scanf("%d %d",&N,&M)){int A, B, S;int ans = 0;for (int i = 0;i <= N;i++)f[i] = i, sum[i] = 0;for (int i = 1;i <= M;i++){scanf("%d %d %d", &A, &B, &S);A--;int x = find(A), y = find(B);if (x != y){f[y] = x;sum[y] = sum[A] + S - sum[B];}else{if (sum[B] - sum[A] != S)ans++;}}printf("%d\n", ans);}return 0; }

E - 食物鏈
經(jīng)典的帶權(quán)并查集題，據(jù)說會做這道題大部分并查集都可以秒了(霧。。)
一開始理解錯(cuò)題意了，沒明白題目這句話，A吃B,B吃C,C吃A。每個(gè)動(dòng)物都是A,B,C中的一種。
所以實(shí)際上動(dòng)物的被吃關(guān)系就組成了一個(gè)環(huán)。
我們現(xiàn)在弄一個(gè)結(jié)構(gòu)體.

struct node {int parent, relation; //relation =0 similar//=1 parent eat this//=2 this eat parent. //so it like vector x->rootxnode(int _p,int _r):parent(_p),relation(_r){}node(){} }nodes[maxn];

relation代表當(dāng)前這個(gè)動(dòng)物和他祖先的關(guān)系(帶權(quán)并查集的relation大多數(shù)都是描述當(dāng)前點(diǎn)和他祖先的關(guān)系，只要找到這個(gè)關(guān)系的數(shù)學(xué)表達(dá)式就能用帶權(quán)并查集！)。
當(dāng)relation=0時(shí)，代表是同類。
當(dāng)relation=1時(shí)，代表祖先吃當(dāng)前動(dòng)物。
當(dāng)relation=2時(shí)，代表當(dāng)前動(dòng)物吃祖先。
現(xiàn)在，我們設(shè)向量AB?→?AB→ 代表A和B的關(guān)系。
當(dāng)|AB?→?AB→|=0時(shí)，代表A和B是同類。
|AB?→?AB→|=1時(shí)，代表B吃A。
|AB?→?AB→|=2時(shí)，代表A吃B。
那么容易發(fā)現(xiàn)結(jié)構(gòu)體的relation其實(shí)相當(dāng)于|AROOTA?→??????AROOTA→|向量。
我們現(xiàn)在來解決find中的路徑壓縮的relation。
a的roota在路徑壓縮過程中先變成了roota2，那么現(xiàn)在a的relation就需要指向roota2了。通過向量我們可以很容易得到:
a->roota2=a->roota+roota->roota2.
所以它的值也就更新成如代碼中所寫的值了。
再看Union。
其實(shí)思考的方式仍然靠向量，唯一需要注意的地方是向量的方向不能弄反了!
我們現(xiàn)在先來看輸入 d x y。
當(dāng)d=1時(shí)，x和y是同類
當(dāng)d=2時(shí)，x吃y。
所以我們把d減1。那么d的值就是代表y->x的值。
再回到Union中。
rooty的祖先先更新成rootx
那么rooty->rootx=rooty->y+y->x+x->rootx。
判斷假話當(dāng)然也是根據(jù)向量，相信讀者根據(jù)上面的想法也能理解判斷的條件，這里就不講啦。。
代碼如下:

#include<iostream> #include<cstring> #include<stdio.h>using namespace std; const int maxn = 5e4 + 5; struct node {int parent, relation; //relation =0 similar//=1 parent eat this//=2 this eat parent. //so it like vector x->rootxnode(int _p,int _r):parent(_p),relation(_r){}node(){} }nodes[maxn]; int find(int idx) {if (nodes[idx].parent != idx){int pre = nodes[idx].parent;nodes[idx].parent = find(nodes[idx].parent);nodes[idx].relation = (nodes[idx].relation + nodes[pre].relation) % 3;}return nodes[idx].parent; } void Union(int x,int y,int rootx, int rooty, int val) {nodes[rooty].parent = rootx;nodes[rooty].relation = (3 - nodes[y].relation + val - 1+nodes[x].relation) % 3; } int main() {int N, K;scanf("%d %d", &N, &K);for (int i = 1;i <= N;i++)nodes[i].parent = i, nodes[i].relation = 0;int opt, x, y, rootx, rooty, ans = 0;for (int i = 1;i <= K;i++){scanf("%d %d %d", &opt, &x, &y);if (x > N || y > N) { ans++;continue; }else if (opt == 2 && x == y) { ans++;continue; }rootx = find(x);rooty = find(y);if (rootx != rooty){Union(x, y, rootx, rooty, opt );}else{if ((nodes[y].relation + 3 - nodes[x].relation) % 3 != opt - 1)ans++;}}cout << ans << endl; }

F - True Liars
目前為止第一道，并查集和其他考點(diǎn)一起運(yùn)用的好題。然而考點(diǎn)一混博主就沒思路了。。。老感覺算法搞清楚了，卻還是做不出題目來。。
回到題目上來，上一題我們就明白了一個(gè)道理，帶權(quán)并查集的relation實(shí)際上就是當(dāng)前節(jié)點(diǎn)與祖先的一個(gè)關(guān)系表示。那么這題如何建立并查集關(guān)系域呢?
聰明的人可以發(fā)現(xiàn)，當(dāng)一個(gè)人說別人是好人的話，那么這個(gè)人和他說的那個(gè)人肯定是一類人，如果說別人是壞人的話，那么這個(gè)人和他說的那個(gè)人肯定不是一類人。
(精華啊！)。
所以relation=0，代表它和祖先是同類，relation=1，代表它和祖先不是同類。
跑一遍并查集后，就可以把整個(gè)大集合分成若干和小集合。每個(gè)集合中有好人也壞人(相對而言)。那么之后就可以設(shè)dp[i][j] 為前i個(gè)集合中好人個(gè)數(shù)為j，同時(shí)可以再開一個(gè)數(shù)組route[i][j] 來記錄路徑。設(shè)集合個(gè)數(shù)為num，那么在跑完之后，看dp[num][p1]是不是等于1.如果等于1，就沿著路徑往前跑就行了。
代碼如下:

#include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<stdio.h> using namespace std; const int maxn = 1005; struct node {int father, relation;node(int _f,int _r):father(_f),relation(_r){}node(){} }nodes[maxn];int find(int idx) {if (nodes[idx].father != idx){int pre = nodes[idx].father;nodes[idx].father = find(pre);nodes[idx].relation = nodes[idx].relation^nodes[pre].relation;}return nodes[idx].father; }void Union(int x,int y,int rootx, int rooty,int val) {if (rootx < rooty)swap(rootx, rooty);nodes[rootx].father = rooty;nodes[rootx].relation = nodes[x].relation^val^nodes[y].relation; } vector<int>V[maxn],IDX,ans; int number[maxn][2]; int route[maxn][maxn]; int dp[maxn][maxn]; bool vis[maxn]; int main() {int n, p1, p2;while (~scanf("%d %d %d", &n, &p1, &p2) &&(n!=0||p1!=0||p2!=0)){memset(vis, 0, sizeof(vis));memset(number, 0, sizeof(number));memset(route, -1, sizeof(route));memset(dp, 0, sizeof(dp));for (int i = 1;i <= p1 + p2;i++)nodes[i] = node(i, 0), V[i].clear();IDX.clear();ans.clear();int a, b, roota, rootb;char s[10];for (int i = 1;i <= n;i++){scanf("%d %d %s", &a, &b, &s);roota = find(a);rootb = find(b);if (roota != rootb){if (s[0] == 'y')Union(a,b,roota, rootb, 0);elseUnion(a,b,roota, rootb, 1);}}for (int i = 1;i <= p1 + p2;i++){int root = find(i);V[root].push_back(i);if (!vis[root])IDX.push_back(root), vis[root] = 1;}int Size = IDX.size();for (int i = 0;i < Size;i++){int theidx = IDX[i];int thesize = V[theidx].size();for (int j = 0;j < thesize;j++){int nodeidx = V[theidx][j];if (!nodes[nodeidx].relation)number[theidx][0]++;elsenumber[theidx][1]++;}}for (int i = 0;i < Size;i++){if (i == 0){int theidx = IDX[0];int number0 = number[theidx][0], number1 = number[theidx][1];dp[0][number0] ++;route[0][number0] = 0;dp[0][number1] ++;route[0][number1] = 1;}else{int theidx = IDX[i];int number0 = number[theidx][0], number1 = number[theidx][1];for (int j = 0;j <= p1 + p2;j++)if (route[i - 1][j] >= 0){dp[i][j + number0] += dp[i - 1][j];route[i][j + number0] = 0;dp[i][j + number1] += dp[i - 1][j] ;route[i][j + number1] = 1;}}}if (dp[Size - 1][p1] == 1){int num = p1;int dep = Size - 1;while (num){int way = route[dep][num];int theidx = IDX[dep];for (int i = 0;i < V[theidx].size();i++){int nodeidx = V[theidx][i];if (nodes[nodeidx].relation == way)ans.push_back(nodeidx);}num -= number[theidx][way];dep--;}sort(ans.begin(), ans.end());for (int i=0;i<ans.size();i++)printf("%d\n", ans[i]);puts("end");}elseputs("no");}return 0; }

G - Supermarket
題意大概就是每個(gè)東西有個(gè)價(jià)值和截止日期，每天能賣一個(gè)東西，問n天后能獲得的最大的價(jià)值是多少。
也是看了題解才恍然大悟，先給東西按價(jià)值從大到小排序，然后用并查集的目的就是最快找到截止日期前沒賣東西的那天。題目和cf的C. String Reconstruction 差不多。。
代碼如下:

#include<iostream> #include<algorithm> #include<cstring> #include<stdio.h> using namespace std; const int maxn = 10005; int f[maxn]; typedef pair<int, int>pii; pii nodes[maxn]; bool cmp(pii a, pii b) {return a.first > b.first; } int find(int a) { return a == f[a] ? a : f[a] = find(f[a]); } void Union(int x, int y) {f[x] = y; } int main() {int n;while (cin>>n){for (int i = 1;i <= 10000;i++)f[i] = i;int p, d;for (int i = 1;i <= n;i++)scanf("%d %d", &nodes[i].first, &nodes[i].second);sort(nodes + 1, nodes + 1 + n, cmp);int ans = 0;for (int i = 1;i <= n;i++){int theday = nodes[i].second;int root = find(theday);if (root > 0){ans += nodes[i].first;Union(root, root - 1);}}cout << ans << endl;} }

H - Parity game
這題思路其實(shí)和之前的差不多，然而length不大于1e9。。數(shù)組根本開不下去。所以這時(shí)候需要離散化后再進(jìn)行并查集。
不是特別熟悉離散化，所以記錄一下這題。

#include<iostream> #include<vector> #include<cstring> #include<algorithm> #include<stdio.h> using namespace std; const int maxn =5005*4 ; int f[maxn], sum[maxn]; struct node {int u, v, ones; }nodes[maxn]; vector<int>V;int find(int a) {if (f[a] != a){int pre = f[a];f[a] = find(f[a]);sum[a] = sum[a] ^ sum[pre];}return f[a]; }void Union(int u, int v, int rootu, int rootv, int val) {f[rootv] = rootu;sum[rootv] = sum[u] ^ val^sum[v]; }int main() {for (int i = 0;i < maxn;i++)f[i] = i, sum[i] = 0;int n;scanf("%d", &n);scanf("%d", &n);char s[10];for (int i = 0;i < n;i++){scanf("%d %d %s", &nodes[i].u, &nodes[i].v, s);if (s[0] == 'e')nodes[i].ones = 0;else nodes[i].ones = 1;V.push_back(nodes[i].u);V.push_back(nodes[i].v);V.push_back(nodes[i].u - 1);V.push_back(nodes[i].v - 1);}sort(V.begin(), V.end());unique(V.begin(), V.end());int i;for ( i = 0;i < n;i++){int uidx = lower_bound(V.begin(), V.end(), nodes[i].u - 1) - V.begin();int vidx = lower_bound(V.begin(), V.end(), nodes[i].v) - V.begin();int rootu = find(uidx);int rootv = find(vidx);if (rootu != rootv)Union(uidx, vidx, rootu, rootv, nodes[i].ones);else{if ((sum[vidx] ^ sum[uidx]) != nodes[i].ones)break;}}cout << i << endl; }

I - Navigation Nightmare
這題比較特別的地方是要開2個(gè)關(guān)系域，一個(gè)代表水平距離，一個(gè)代表垂直距離。另外注意方向即可。

#include<iostream> #include<vector> #include<cstring> #include<stdio.h> #include<math.h> #include<stdlib.h> using namespace std; const int maxn = 40005; const int maxm = 40005; int f[maxn], sum1[maxn], sum2[maxn]; struct query {int u, v, dis;char s[3]; }Q[maxm]; typedef pair<int, int>pii; vector<pii>V[maxm];int find(int a) {if (f[a] != a){int pre = f[a];f[a] = find(f[a]);sum1[a] += sum1[pre];sum2[a] += sum2[pre];}return f[a]; }void Union(int u, int v, int rootu, int rootv, int val, char *s) {int tmp1, tmp2;if (s[0] == 'N')tmp1 = val, tmp2 = 0;else if (s[0] == 'E')tmp1 = 0, tmp2 = val;else if (s[0] == 'W')tmp1 = 0, tmp2 = -val;elsetmp1 = -val, tmp2 = 0;//if (rootu < rootv)swap(rootu, rootv);f[rootu] = rootv;sum1[rootu] = -sum1[u] + tmp1 + sum1[v];sum2[rootu] = -sum2[u] + tmp2 + sum2[v]; }int main() {int N, M;scanf("%d %d", &N, &M);for (int i = 1;i <= N;i++)f[i] = i, sum1[i] = 0, sum2[i] = 0;for (int i = 1;i <= M;i++){scanf("%d %d %d %s", &Q[i].u, &Q[i].v, &Q[i].dis, Q[i].s);}int q;scanf("%d", &q);int u, v, idx;while (q--){scanf("%d %d %d", &u, &v, &idx);V[idx].push_back(pii(u, v));}int rootu, rootv;for (int i = 1;i <= M;i++){u = Q[i].u, v = Q[i].v;rootu = find(u);rootv = find(v);if (rootu != rootv)Union(u, v, rootu, rootv, Q[i].dis, Q[i].s);int Size = V[i].size();for (int j = 0;j < Size;j++){u = V[i][j].first, v = V[i][j].second;rootu = find(u);rootv = find(v);if (rootu != rootv)puts("-1");else{int dist1 = sum1[u] - sum1[v], dist2 = sum2[u] - sum2[v];int dis = abs(dist1) + abs(dist2);printf("%d\n", dis);}}}return 0; }

K - Rochambeau
枚舉裁判，然后并查集判斷

裁判由于可以任意出，所以可能屬于任意一個(gè)集合，所以有裁判參與的會合不考慮，然后并查集部分和食物鏈很相似。

如果某個(gè)裁判那里出現(xiàn)了矛盾，則記錄一下在哪出問題。

然后判斷是否只有一個(gè)裁判沒有出現(xiàn)問題。如果只有一個(gè)，說明可以確定，那么就是剩下的人出問題的最大值。枚舉裁判，然后并查集判斷

裁判由于可以任意出，所以可能屬于任意一個(gè)集合，所以有裁判參與的會合不考慮，然后并查集部分和食物鏈很相似。

如果某個(gè)裁判那里出現(xiàn)了矛盾，則記錄一下在哪出問題。

然后判斷是否只有一個(gè)裁判沒有出現(xiàn)問題。如果只有一個(gè)，說明可以確定，那么就是剩下的人出問題的最大值。因?yàn)橹挥蟹穸似渌腥硕疾皇遣门?#xff0c;才能確定他是裁判。

#include<iostream> #include<cstring> #include<stdio.h> #include<string> #include<algorithm> using namespace std; const int maxn = 505; const int maxm = 2005; const int inf = 0x3f3f3f3f; int f[maxn], sum[maxn]; int find(int a) {if (f[a] != a){int pre = f[a];f[a] = find(f[a]);sum[a] = (sum[a] + sum[pre]) % 3;}return f[a]; }void Union(int u, int v, int rootu, int rootv, int val) {f[rootu] = rootv;sum[rootu] = (3 - sum[u] + val + sum[v]) % 3; } string s[maxm]; int main() {int N, M;while (~scanf("%d %d", &N, &M)){for (int i = 0;i < M;i++)cin >> s[i];int ansnum = 0, ansidx = 0,ans;for (int i = 0;i < N;i++){for (int j = 0;j < N;j++)f[j] = j, sum[j] = 0;//bool flag = true;int j;int tmp;for ( j = 0;j < M;j++){int Size = s[j].size();int num, u, v, rootu, rootv;for (int t = 0;t < Size;t++){if(s[j][t]=='='){num = 0;break;}else if (s[j][t] == '>'){num = 1;break;}else if (s[j][t] == '<'){num = 2;break;}}if (num == 0)sscanf(s[j].c_str(), "%d=%d", &u, &v);else if (num == 1)sscanf(s[j].c_str(), "%d>%d", &u, &v);else sscanf(s[j].c_str(), "%d<%d", &u, &v);if (u == i || v == i)continue;rootu = find(u);rootv = find(v);if (rootu != rootv)Union(u, v, rootu, rootv, num);else{if ((sum[u] + 3 - sum[v]) % 3 != num){tmp = j + 1;break;}}}if (j == M){ansnum++;ans = i;}elseansidx = max(ansidx, tmp);}if (ansnum > 1)puts("Can not determine");else if (ansnum == 0)puts("Impossible");else printf("Player %d can be determined to be the judge after %d lines\n", ans, ansidx);}return 0; }

M - 小希的迷宮
題目簡單但有幾個(gè)坑點(diǎn)。
1，不能有森林。(博主注意到了)
2，指向自己的應(yīng)該也算可行。(注意到了,不過好像沒這樣的數(shù)據(jù)。。)
3,一開始輸入0 0也算。。(很無語。。)
代碼如下:

#include<iostream> #include<stdio.h> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn = 100005; int f[maxn]; int find(int a) { return a == f[a] ? a : f[a] = find(f[a]); } void Union(int a, int b) { if (a > b)swap(a, b);f[b] = a; } vector<int>V; int main() {int u, v,rootu,rootv;while (~scanf("%d %d",&u,&v)&&(u!=-1||v!=-1)){if (u == 0 && v == 0){puts("Yes");continue;}V.clear();for (int i = 1;i < maxn;i++)f[i] = i;rootu = find(u);rootv = find(v);V.push_back(u);V.push_back(v);Union(rootu, rootv);bool flag = true;while (~scanf("%d %d",&u,&v)&&(u!=0||v!=0)){//if (u == v)continue;V.push_back(u);V.push_back(v);rootu = find(u);rootv = find(v);if (rootu == rootv){flag = false;puts("No");//break;}elseUnion(rootu, rootv);}if (flag){sort(V.begin(), V.end());unique(V.begin(), V.end());int theroot = find(V[0]);for(int i=1;i<V.size();i++)if (find(V[i]) != theroot){flag = false;break;}if (flag)puts("Yes");else puts("No");}}}

N - Is It A Tree?
這題和上題差不多，但有點(diǎn)細(xì)節(jié)不同。
1，空樹算。
2，指向自己的不算。
3，森林不算。
注意細(xì)節(jié)就好！

#include<iostream> #include<stdio.h> #include<cstring> #include<set> #include<algorithm> using namespace std; const int maxn = 100005; int f[maxn]; int find(int a) { return a == f[a] ? a : f[a] = find(f[a]); } void Union(int a, int b) { if (a > b)swap(a, b);f[b] = a; } set<int>V; void init() {for (int i = 1;i < maxn;i++)f[i] = i;V.clear(); } int main() {int u, v,rootu,rootv;int cas = 1;bool flag = 1;init();while (~scanf("%d %d",&u,&v)&&(u!=-1||v!=-1)){if (u == 0 && v == 0){if (flag){int cnt = 0,tmp;for (set<int>::iterator it = V.begin();it != V.end();it++){if (it == V.begin())tmp = find(*it), cnt++;else if (tmp != find(*it))cnt++;}if (cnt > 1)flag = 0;}if (flag)printf("Case %d is a tree.\n", cas++);else printf("Case %d is not a tree.\n", cas++);init();flag = 1;continue;}rootu = find(u);rootv = find(v);if (rootu == rootv)flag = 0;elseUnion(rootu, rootv);V.insert(u);V.insert(v);}}

哇，做題一定要注意細(xì)節(jié)，追求1A率!

總結(jié)

以上是生活随笔為你收集整理的kuangbin专题五并查集总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。