本次训练共5题，本文附AC代码和题目链接。

之前已经学过并查集和最小生成树了(<stron>)</stron>，今天在洛谷上面复习一下。

洛谷 P1536 村村通

#include <bits/stdc++.h>
using namespace std;
const int N=1010,M=2e5+10;
int n,m,cnt,ans,pre[N];
struct node
{
    int x,y;
}p[M<<1];
int find(int x)
{
    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
void join(int a,int b)
{pre[find(a)]=find(b);}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        cin>>m;
        for(int i=1;i<=n;i++)
            pre[i]=i;
        for(int i=1;i<=m;i++)
            cin>>p[i].x>>p[i].y;
        cnt=0;
        for(int i=1;i<=m;i++)
        {
            if(find(p[i].x)!=find(p[i].y))
            {
                cnt++;
                join(p[i].x,p[i].y);
            }
            if(cnt==n-1)break;
        }
        cnt==n-1?printf("0\n"):printf("%d\n",n-1-cnt);
    }
    return 0;
}

洛谷 P3366 【模板】最小生成树

#include <bits/stdc++.h>
using namespace std;
const int N=5010,M=2e5+10;
int n,m,cnt,ans,pre[N];
struct node
{
    int x,y,val;
}p[M<<1];
bool cmp(node a,node b)
{return a.val<b.val;}
int find(int x)
{
    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
void join(int a,int b)
{pre[find(a)]=find(b);}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        pre[i]=i;
    for(int i=1;i<=m;i++)
        cin>>p[i].x>>p[i].y>>p[i].val;
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(p[i].x)!=find(p[i].y))
        {
            cnt++;
            join(p[i].x,p[i].y);
            ans=ans+p[i].val;
        }
        if(cnt==n-1)break;
    }
    cnt<n-1?printf("orz\n"):printf("%d\n",ans);
    return 0;
}

洛谷 P1547 Out of Hay

#include <bits/stdc++.h>
using namespace std;
const int N=2010,M=1e4+10;
int n,m,k,mx,cnt,pre[N];
struct node
{
    int x,y,val;
}p[M<<1];
bool cmp(node a,node b)
{return a.val<b.val;}
int find(int x)
{
    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
void join(int a,int b)
{pre[find(a)]=find(b);}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        pre[i]=i;
    for(int i=1;i<=m;i++)
        cin>>p[i].x>>p[i].y>>p[i].val;
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(p[i].x)!=find(p[i].y))
        {
            cnt++;
            join(p[i].x,p[i].y);
            mx=max(mx,p[i].val);
        }
        if(cnt==n-1)break;
    }
    printf("%d\n",mx);
    return 0;
}

洛谷 P1195 口袋的天空

#include <bits/stdc++.h>
using namespace std;
const int N=1010,M=1e4+10;
int n,m,k,cnt,ans,pre[N];
struct node
{
    int x,y,val;
}p[M<<1];
bool cmp(node a,node b)
{return a.val<b.val;}
int find(int x)
{
    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
void join(int a,int b)
{pre[find(a)]=find(b);}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        pre[i]=i;
    for(int i=1;i<=m;i++)
        cin>>p[i].x>>p[i].y>>p[i].val;
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(p[i].x)!=find(p[i].y))
        {
            cnt++;
            join(p[i].x,p[i].y);
            ans=ans+p[i].val;
        }
        if(cnt==n-k)break;//如果要连成k个连通分量，则要连的边的数量必然为n-k(可以由单个树的性质m=n-1得到)
    }
    cnt<n-k?printf("No Answer\n"):printf("%d\n",ans);
    return 0;
}

洛谷 P2820 局域网

“除去一些边，使得网络中没有回路，并且被除去网线的权值和最大”
等价于“找到网络的最小生成树(连n-1条边，且它们的权值和最小)”。

#include <bits/stdc++.h>
using namespace std;
const int N=110,M=1e4+10;
int n,m,k,cnt,val,sum,pre[N];
struct node
{
    int x,y,val;
}p[M<<1];
bool cmp(node a,node b)
{return a.val<b.val;}
int find(int x)
{
    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
void join(int a,int b)
{pre[find(a)]=find(b);}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        pre[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>p[i].x>>p[i].y>>p[i].val;
        sum=sum+p[i].val;
    }
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(p[i].x)!=find(p[i].y))
        {
            cnt++;
            join(p[i].x,p[i].y);
            val=val+p[i].val;
        }
        if(cnt==n-1)break;
    }
    printf("%d\n",sum-val);
    return 0;
}