文章目录
P1525 [NOIP2010提高组] 关押罪犯
P1525 [NOIP2010 提高组] 关押罪犯
题意：
题意是有
N
N
N
个罪犯，将他们划分成两个集合，有一些罪犯之间有带权边（一共有
M
M
M
条），如果他们在同一集合中，此边就存在，求如何划分，使得存在的最大的边权最小。
对于
100
%
100\%
1
0
0
%
的数据有
N
≤
20000
,
M
≤
100000
N\leq 20000,M\leq 100000
N
≤
2
0
0
0
0
,
M
≤
1
0
0
0
0
0
。
关键字眼：划分为
两个集合
，
最大边权最小
贪心策略
策略：尽可能让仇恨值最大的罪犯在两个不同的监狱中
将罪犯划分入一个集合中，可能会同时产生几条新边，按某种规则将罪犯逐一划入两个监狱，可能不经意间就将仇恨值最大的罪犯划分在一起，不好确定如何划分，所以考虑将罪犯分开。
将罪犯之间的边按边权由大到小排序。
朴素并查集
枚举当前最大的仇恨值的边，让当前仇恨值最大的罪犯在两个不同的监狱中，根据“朋友的朋友是朋友，敌人的敌人是朋友”的原则，将这两名罪犯划分入不同的监狱中，如果当前仇恨值最大的罪犯已经在同一个监狱中，那么当前最大仇恨值就是答案。
for(int i = 1;i <= m;i ++)
{
if(judge(e[i].from,e[i].to))
{
ans = e[i].val;
break;
}
if(ag[e[i].from] > 0) join(ag[e[i].from],e[i].to);//ag[i] 表示 i 的敌人，即不连边的两个罪犯
else ag[e[i].from] = e[i].to;
if(ag[e[i].to] > 0) join(ag[e[i].to],e[i].from);
else ag[e[i].to] = e[i].from;
}
种类并查集（扩展域并查集）
继续考虑“敌人的敌人是朋友”这一原则，根据以上的做法可以引申出种类并查集（又称扩展并查集）的做法。
考虑“敌人的敌人是朋友”这一原则，用一个并查集维护罪犯之间的关系，称之为原域，为了记录敌人，再开一个并查集，称之为扩展域。
现在假设
i
i
i
与
j
j
j
敌对，那么根据上述定义，令原域的
i
i
i
与扩展域的
j
j
j
连边，再令原域的
j
j
j
与扩展域的
i
i
i
连边，表达敌对关系。若此时有另一敌对关系
(
j
,
k
)
(j,k)
(
j
,
k
)
，那么完成连边后，可以得到下图：
这时我们可以发现，如果我们在原域查询
i
,
k
i,k
i
,
k
，可以得到友好关系，完成了“敌人的敌人是朋友”的表达。
由此可知：种类并查集可以维护对立关系，而且可以维护多对等价双向的对立关系，可以维护“敌人的敌人是朋友”这一原则。
int main()
{
scanf("%d%d",&N,&M);
for(int i = 1;i <= M;i++)
scanf("%d%d%d",&r[i].a,&r[i].b,&r[i].c);
sort(r + 1,r + 1 + M,cmp);
for(int i = 1;i <= N*2/*增设扩展域*/;i ++) fa[i] = i;
for(int i = 1;i <= M;i ++)
{
if(judge(r[i].a,r[i].b))
{
printf("%d",r[i].c);
return 0;
}
merge(r[i].a,r[i].b + N);//由于对立关系有对称性
merge(r[i].b,r[i].a + N);//所以要录入两次
}
printf("0");
return 0;
}
带权并查集
我们可以考虑只用一倍空间的并查集，但是运用完全不一样的思路。
对于“敌人的敌人是朋友”这一原则，我们考虑用模 2 运算表达，那么每次连边合并，我们就要赋予边权。
现在考虑实现以下要求：
- 敌人之间的路径权值模 2 为 1
- 朋友之间的路径权值模 2 为 0
容易想到以下构造：
黑色标号为加边的顺序，红色标号为边的权值，那么这个关系是
r
t
rt
r
t
与
f
x
f_x
f
x
敌对，
f
x
f_x
f
x
与
x
x
x
敌对，而
r
t
rt
r
t
与
x
x
x
友好，同时它们之间的路径权值和模 2 为 0.
现在我们定义
v
a
l
(
x
)
val(x)
v
a
l
(
x
)
表示
x
x
x
到父亲结点的路径上的权值和。
考虑能否在带权并查集上实现路径压缩
可以实现路径压缩，但是路径压缩的过程中，被压缩掉的边的权值和要记录下来，并与结点到父结点的边权一同组成新边权，这条新边从这个结点到根结点。
v
a
l
′
(
x
)
=
v
a
l
(
x
)
+
S
val'(x) = val(x) + S
v
a
l
′
(
x
)
=
v
a
l
(
x
)
+
S
其中
S
S
S
可以在递归的过程中计算出，并最后赋值在
v
a
l
′
(
f
x
)
val'(f_x)
v
a
l
′
(
f
x
)
代码如下：
int findx(int x)
{
int tmp = fa[x];
if(tmp != x)
{
fa[x] = findx(fa[x]);
val[x] = (val[x] + val[tmp])%2'
return fa[x];
}
else return tmp;
}
考虑如何合并两点所在的两个不同的集合
合并两点所在的两个不同集合，关键在于修改这两个集合的根之间的边的权值，即知道
x
x
x
与
f
x
f_x
f
x
之间的关系，知道
y
y
y
与
f
y
f_y
f
y
之间的关系，知道
x
x
x
与
y
y
y
的关系，求
f
x
f_x
f
x
与
f
y
f_y
f
y
之间的关系。
现在我们压缩路径之后，得到
v
a
l
(
x
)
val(x)
v
a
l
(
x
)
表示
x
x
x
到根结点的边权和。
所以在合并两个结合的时候，要修改
x
x
x
的根结点
f
x
f_x
f
x
到
f
y
f_y
f
y
的权值，令权值
v
a
l
(
f
x
)
=
v
a
l
(
y
)
−
v
a
l
(
x
)
+
r
val(f_x) = val(y) – val(x) + r
v
a
l
(
f
x
)
=
v
a
l
(
y
)
−
v
a
l
(
x
)
+
r
void join(int x,int y)
{
int rx = findx(x);int ry = findx(y);
fa[rx] = ry;
val[rx] = (((val[y] - val[x])%2 + 2)%2 + 1) % 2;
return ;
}
考虑如何计算两点间的权值
一般来说，只有当两点在同一连通块中才可以计算两点间的权值，那么令
x
x
x
到根结点的权值和为
v
a
l
(
x
)
val(x)
v
a
l
(
x
)
，令
y
y
y
到根结点的权值和为
v
a
l
(
y
)
val(y)
v
a
l
(
y
)
，同样观察上图的情况，可以得到
r
=
v
a
l
(
x
)
−
v
a
l
(
y
)
r = val(x) – val(y)
r
=
v
a
l
(
x
)
−
v
a
l
(
y
)
综上，我们得到了带权并查集的基本操作，于是就可以运用它来解题。
int findx(int x)//以后还是严格按照这个格式写，否则容易出错
{
int tmp = fa[x];
if(tmp != x)
{
fa[x] = findx(tmp);
val[x] = (val[x] + val[tmp])%2;//压缩权值
return fa[x];
}
else return tmp;
}
void join(int x,int y)
{
int rx = findx(x);int ry = findx(y);
fa[rx] = ry;
val[rx] = (((val[y] - val[x])%2 + 2)%2 + 1) % 2;//更新其中一个根结点与它的新父亲的边的权值
return ;
}
int main()
{
scanf("%d%d",&N,&M);
for(int i = 1;i <= M;i ++)
scanf("%d%d%d",&r[i].a,&r[i].b,&r[i].c);
sort(r + 1,r + 1 + M,cmp);
for(int i = 1;i <= N;i ++) fa[i] = i,val[i] = 0;
for(int i = 1;i <= M;i ++)
{
int ra = findx(r[i].a);int rb = findx(r[i].b);
if(ra != rb) join(r[i].a,r[i].b);
else
{
int newrel = ((val[r[i].a] - val[r[i].b])%2 + 2)%2;//计算两点间的权值
if(newrel == 0)
{
printf("%d",r[i].c);
return 0;
}
}
}
二分图判定
将两个罪犯分开看作一种对立关系，在他们之间连不带权的边，然后每次分开跑一次二分图判定，直至判定失败时那对罪犯之间的仇恨值即为答案。
二分答案策略
二分图判定
二分最大的仇恨值，同理将两个罪犯分开看作对立关系，将所有权值小于二分答案的边所对应的罪犯连边，跑二分图判定，如果判定成功则尝试令答案更小，否则令二分的答案增大继续尝试。
小结
本题一题多解，灵活变通，是锻炼思维的好题目。从中我们也可以学习到多种多样的知识点。