HDU 6187 Destroy Walls（并查集）

Edie ·

更新时间:2024-09-21

· 883 次阅读

题意：
给定n个点，m条边，实现将全部点连通（最小生成树），即去掉回路（环），所需的最少费用。

思路：
n太大，prim算法会超时。
使用并查集+贪心：先将已有边的权值从大到小排序，又n个点只需n-1条边，这时再遍历一遍，将有边的两点合并为一个队伍，当边的数量达到n-1时退出循环，因为此时已达到最小生成树。
边的权值由大到小排序是因为要将大的权值用来合并，剩下的小权值的边便能使得拆除时所用的费用尽量小。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x7fffffff
using namespace std;
const int maxn=100000+5;
int fa[maxn],n,m;
struct node
{
    int u,v,w;
    bool operatort.w;
    }
}a[maxn*2];
int Find(int x)
{
    if(x!=fa[x])
        fa[x]=Find(fa[x]);
    return fa[x];
}
int main()
{
    ios::sync_with_stdio(false);
    int x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
            fa[i]=i;
        int s=0,sum=0;
        int num=0;
        while(n--)
        {
            scanf("%d%d",&x,&y);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
            sum+=a[i].w;
        }
        sort(a,a+m);
        for(int i=0;i<m;i++)
        {
            int x=Find(a[i].u),y=Find(a[i].v);
            if(x!=y)
            {
                fa[x]=y;
                s+=a[i].w;
                num++;
                if(num==n-1)
                    break;
            }
        }
        int res=sum-s;
        printf("%d %d\n",m-num,res);
    }
    return 0;
}

作者：AimerAimerAimer

hdu 并查集

1024 个赞