M_sea

洛谷1525 关押罪犯
Luogu分析这道题要用贪心+并查集来做。每次选择一对有最大仇恨的罪犯,放在两个牢房里。当这两个罪犯已在同一牢房时...
扫描右侧二维码阅读全文
14
2017/09

洛谷1525 关押罪犯

Luogu

分析

这道题要用贪心+并查集来做。

每次选择一对有最大仇恨的罪犯,放在两个牢房里。当这两个罪犯已在同一牢房时,输出并退出。

然后可以用并查集维护牢房关系。

用hate数组来维护每个罪犯的仇人,并查集来维护当前牢房即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
struct node //仇敌关系
{
    int x,y;
    int z;
    node()
    {
        this->x=this->y=0;
        this->z=0;
    }
};
node f[100005];
int root[20005],hate[20005]; //并查集&仇敌
inline bool cmp(const node a,const node b) { return a.z>b.z; } //sort用
inline int find(int x) //查询根节点
{
    if (root[x]!=x) root[x]=find(root[x]);
    return root[x];
}
inline void merge(int x,int y) //合并
{
    x=find(x); y=find(y);
    root[x]=y;
}
inline bool check(int x,int y) //检查是否在同一集合
{
    x=find(x); y=find(y);
    return (x==y);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (re int i=1;i<=n;i++) root[i]=i; //初始化
    for (re int i=1;i<=m;i++) scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z); //输入
    sort(f+1,f+m+1,cmp); //排序
    for (re int i=1;i<=m;i++) //贪心过程
    {
        if (check(f[i].x,f[i].y)) //如果两个罪犯已经在同一监狱就输出
        {
            printf("%d\n",f[i].z);
            return 0;
        }
        else
        {
            if (!hate[f[i].x]) hate[f[i].x]=f[i].y; //标记“敌人”
            else merge(hate[f[i].x],f[i].y); //将敌人的敌人合并
            if (!hate[f[i].y]) hate[f[i].y]=f[i].x; //同上
            else merge(hate[f[i].y],f[i].x);
        }
    }
    printf("0\n"); //没有冲突,输出0
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 09 PM

发表评论