题解 P1525 【关押罪犯】

· · 题解

这道题我们可以把它当做边带全的并查集来做。

但其实并查集的做法并不是特别好想，我一开始的时候却把它当成了二分图来做，看了一下别人的题解我才知道这是一个并查集的题。

那么什么是并查集呢？

转并查集

如果你没有听懂，那就算了

废话不多说，我来讲一下并查集；

并查集

并查集是一种可以动态维护若干个不重叠的集合，并支持合并与 询的数据结构，详细地说，并查集包括如下两个基本操作:

1.find，查询一个元素属于哪一个集合。

2.merge （我习惯叫他hb（合并（hebing））），把两个集合合并成一个大集合。

为了具体实现并查集这种数据结构，我们首先需要定义集合的表示方法。

在并查集中，我们采用 “找爹”法，即为每个集合选择一个固定的元素，作为整个集合的 “爹”，

其次，我们需要定义归属关系的表示方法。第一种思路是维护一个数组f，用f 保存元素x所在集合的 “爹”。这种方法可以快速查询元素的归属集合，但在合并时需要修改大量元素的f值，效率很低。

第二种思路是使用一棵树形结构存储每个集合，树上的每个节点都是一个元素，树根是集合的代表元素。

整个并查集实际上是一个森林(若干棵树)，我们仍然可以维护一个数组fa来记录这个森林，用fa[x]保存x的父节点。

特别地，令树根的fa值为它自己。

这样一来，在合并两个集合时，只需接两个树根(令其中ー个树根为另ー个树根的子节点，即 fa[root1]＝root2，不过在查询元素的归属时，需要从该元素开始通过fa存储的值不断递归访间父节点，直至到达树根。

为了提高查询效率，并查集引入了路径压缩与按秩合并两种思想。

本蒟蒻若对按秩合并不太熟悉。

所以下面对路径压缩详细讲解（逃）

路经压缩

大家可能已经注意到，第一种思路(直接用数组f保存代表)的査询效率很高，我 们不妨考虑把两种思路进行结合。

实际上，我们只关心每个集合对应的“树形结构”的根节点是什么，并不关心这棵树的具体形态

因此，我们可以在每次执行find操作的同时，把访问过的每个节点(也就是所查询元素全部祖先)都直接指向树根。

代码实现

并查集的初始化

for(int i=1;i<=cnt;i++)
    {
        f[i]=i;
    }

find操作

int find(int x)
{
    if(x!=f[x])f[x]=find(f[x]);
    return f[x];
}

合并操作

void add(int x,int y)
{
    x=find(f[x]);
    y=find(f[y]);
    f[x]=y;
}

判断操作

bool check(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return true;
    return false;
}

sort的cmp

bool cmp(zf x,zf y)
{
    return x.c>y.c;
}

结构体

struct zf{
    int a;
    int b;
    int c;
}x[100010];

主函数

int main()
{
    scanf("%d%d",&n,&m);//输入
    for(i=1;i<=n;i++)//初始化
    a[i]=i;
    for(i=1;i<=m;i++)
    {
         scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].c);//输入
    }
    sort(x+1,x+m+1,cmp);//排序，STL大法好！！！！
    for(i=1;i<=m+1;i++)
    {
        if(check(x[i].a,x[i].b))
        {
            printf("%d",x[i].c);//如果两个罪犯已经在同一监狱就输出
            break;//退出循环
        }
            else 
        {
            if(!b[x[i].a])b[x[i].a]=x[i].b;//标记敌人
            else
            {
                hb(b[x[i].a],x[i].b);合并敌人的敌人；
            }
            if(!b[x[i].b])b[x[i].b]=x[i].a;//相反亦然
            else
            {
                hb(b[x[i].b],x[i].a);
            }
        }
    }
    return 0;//华丽的结束~-~
}

废话不多说，上完整代码；

#include<bits/stdc++.h>
using namespace std;
struct zf{
    int a;
    int b;
    int c;
}x[100010];

int n,m,a[20015],b[20015],i;

inline bool cmp(zf x,zf y)
{
    return x.c>y.c;
}
inline int find(int x)
{
    if(a[x]==x)return x;
    a[x]=find(a[x]);
    return a[x];
}
inline void hb(int x,int y)
{
    x=find(a[x]);
    y=find(a[y]);
    a[x]=y;
}
inline bool check(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return true;
    return false;
}

int main()
{
    scanf("%d%d",&n,&m);

    for(i=1;i<=n;i++)
    a[i]=i;

    for(i=1;i<=m;i++)
    {
         scanf("%d%d%d",&x[i].a,&x[i].b,&x[i].c);
    }
    sort(x+1,x+m+1,cmp);

    for(i=1;i<=m+1;i++)
    {
        if(check(x[i].a,x[i].b))
        {
            printf("%d",x[i].c);
            break;
        }
        else 
        {
            if(!b[x[i].a])b[x[i].a]=x[i].b;
            else hb(b[x[i].a],x[i].b);
            if(!b[x[i].b]) b[x[i].b]=x[i].a;
            else hb(b[x[i].b],x[i].a);
        }
    }
    return 0;
}

注释上面有，就不写了（逃）~

完结 最后安利一下我的博客 （逃）

如果本蒟蒻题解写的不够好或者有哪些地方不够精确，请在评论里面留言。

望满意~~

题解写的不容易。希望审核大佬手下留情 逃