并查集（第二部分）

關押罪犯(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;
}