并查集（第二部分）

关押罪犯(LibreOJ-2594)(Normal)

并查集+虚点

int a[];
int n;
int x;
//a[x]的虚点就是a[x+n]
           

1.首先需要排序，这样我们才能使怒气值更加小

2.如果罪犯x会和罪犯y冲突，那么就将x和y的虚点连起来，y和x的虚点连起来。

3.最后，如果x和y都连接到了同一个点的虚点，那么就可以输出它们的怒气值了，因为我们已经对怒气值排过序了，排完更大的，现在冲突的就是剩下的中最大的，直接输出就可以了，如果过完了这个循环还没有找到，说明能分配完，输出0就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20000*2+5;
const int M=100000+5;
//对事件的处理
struct node
{
    int a;
    int b;
    int w;
}f[M];
bool cmp(node x,node y)
{
    return x.w>y.w;
}
int p[N];
//找根节点
int find(int x)
{
    if(p[x]!=x)
    p[x]=find(p[x]);
    return p[x];
}
//合并
void merge(int x,int y)
{
    p[find(x)]=find(y);
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=2*n;i++)
        p[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d %d %d",&f[i].a,&f[i].b,&f[i].w);
    sort(f+1,f+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(f[i].a)!=find(f[i].b))
        {
            merge(f[i].a+n,f[i].b);
            merge(f[i].a,f[i].b+n);
        }
        else
        {
            printf("%d\n",f[i].w);
            return 0;
        }

    }
    printf("0\n");
    return 0;
}


           

程序自动分析（LibreOJ-2129）（easy）

数据过大，需要离散化。

由题意我们可以知道，我们可以先判断相等时的约束条件，形成并查集，然后再判断不等条件，查看是否与之前矛盾。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=2000000+10;
unordered_map<int,int>mp;
int p[N];
int idx;
struct Query
{
    int x;
    int y;
    int e;
}query[N];
int find(int x)
{
    if(p[x]!=x)
    p[x]=find(p[x]);
    return p[x];
}
int get(int x)
{
    if(!mp.count(x))
    mp[x]=idx++;
    return mp[x];
}  //离散化
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        idx=0;
        mp.clear();
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            int x,y,e;
            cin>>x>>y>>e;
            query[i]={get(x),get(y),e};
        }
        for(int i=0;i<idx;i++)
        p[i]=i;
        for(int i=0;i<n;i++)
        {
            if(query[i].e==1)
            {
                int pa=find(query[i].x);
                int pb=find(query[i].y);
                p[pa]=pb;
            }
        }
        bool flag=true;
        for(int i=0;i<n;i++)
        {
            if(query[i].e==0)
            {
                int pa=find(query[i].x);
                int pb=find(query[i].y);
                if(pa==pb)
                {
                    flag=false;
                    break;
                }
            }
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}


           

修复公路（计蒜客-T1663）（easy）

模板题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=1000+5;
const int M=100000+5;
int p[N];
struct node
{
    int x;
    int y;
    int t;
}f[M];
bool cmp(node a,node b)
{
    return a.t<b.t;
}
int find(int x)
{
    if(p[x]!=x)
    p[x]=find(p[x]);
    return p[x];
}
int merge(int x,int y)
{
    p[find(x)]=find(y);
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=1;i<=m;i++)
    scanf("%d %d %d",&f[i].x,&f[i].y,&f[i].t);
    sort(f+1,f+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(f[i].x)!=find(f[i].y))
        {
            p[find(f[i].x)]=find(f[i].y);
            n--;
        }
        if(n==1)
        {
            printf("%d\n",f[i].t);
                return 0;
        }
    }
    printf("-1\n");
    return 0;
}