NOIP2010 T3(拆点并查集/带权并查集)

两种做法,思路都差不多,排序后从大的边权一直做就行了。我把之前做的代码放上来了。

带权并查集:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
struct node {
int x;
int y;
int v;
bool operator <(node const &a) const {//重载符号以排序
return v>a.v;
}
}zf[100005];//罪犯
int n, m;
int father[20005];//并查集
int r[20005];//指出的权值 1表示在同一监狱 0表示不在同一监狱
int find(int x){//并查集找根+路径压
if (father[x] == x) return x;
int t = find(father[x]);
r[x] = (r[x] + r[father[x]]) % 2;
return father[x] = t;
}
int main(){
scanf("%d%d", &n, &m);
for (int i=1;i<=n;i++) father[i] = i;
for (int i=1;i<=m;i++) scanf("%d%d%d", &zf[i].x, &zf[i].y, &zf[i].v);//输入
sort(zf + 1, zf + 1 + m);//排序
for (int i=1;i<=m;i++) {
int a = zf[i].x, b = zf[i].y, x = find(a), y = find(b);
if (x != y) {
father[x] = y;
r[x] = (r[b] - r[a] + 1 + 2) % 2;
} else {
if ((r[b] - r[a] + 1) % 2) {printf("%d\n", zf[i].v); return 0;}
}
}
printf("%d\n", 0);
return 0;
}

拆点并查集:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
struct node {
int x;
int y;
int v;
bool operator <(node const &a) const {//重载符号以排序
return v>a.v;
}
}zf[100005];//罪犯
int n, m;
int father[40005];//并查集
int find(int x) {//并查集找根+路径压缩
return father[x] == x ? x : father[x] = find(father[x]);
}
int merge(int x, int y) {//并查集合并
int x1 = find(x), y1 = find(y);
father[y1] = x1;
}
int main(){
scanf("%d%d", &n, &m);
for (int i=1;i<=2*n;i++) father[i] = i;
for (int i=1;i<=m;i++) scanf("%d%d%d", &zf[i].x, &zf[i].y, &zf[i].v);//输入
sort(zf + 1, zf + 1 + m);//排序
for (int i=1;i<=m;i++)
{
int x1 = find(zf[i].x), y1 = find(zf[i].y);
if (x1 != y1)//不在同一监狱
{
merge(zf[i].x, zf[i].y + n);
merge(zf[i].y, zf[i].x + n);//合并虚结点
} else {printf("%d\n", zf[i].v);return 0;}
}
printf("%d\n", 0);
return 0;
}

------ 本文结束 ------