HDU 1232（最小生成树；并查集）

淩亂°似流年 2022-09-20 11:28 177阅读 0赞

题意：如题。

最小生成树建模方法：已有的边的花费为0，不存在的边花费为1，求最小生成树。

#include<cstdio>
    #include<cstring>
    using namespace std;
    #define Inf 0x7fffffff
    int map[1005][1005];
    int Prim(int s)
    {
    	int i,j,k,dis[1005],temp,flag,ans=0;
    	bool visit[1005];
    	for(i=0;i<1005;i++)
    		dis[i]=map[0][i];
    	memset(visit,false,sizeof(visit));
    	visit[0]=true;
    	for(i=0;i<s-1;i++)
    	{
    		temp=Inf;
    		for(j=1;j<=s-1;j++)
    		{
    			if(temp>dis[j]&&!visit[j])
    			{
    				temp=dis[j];
    				flag=j;
    			}
    		}
    		visit[flag]=true;
    		for(k=1;k<=s-1;k++)
    			if(map[flag][k]<dis[k]&&!visit[k])
    				dis[k]=map[flag][k];
    		ans+=temp;
    	}
    	return ans;
    }
    int main()
    {
    	int i,j,n,m,a,b,ans;
    	while(scanf("%d",&n)!=-1&&n)
    	{
    		scanf("%d",&m);
    		for(i=0;i<n;i++)
    			for(j=0;j<n;j++)
    				map[i][j]=1;
    		for(i=0;i<m;i++)
    		{
    			scanf("%d%d",&a,&b);
    			map[a-1][b-1]=map[b-1][a-1]=0;
    		}
    		ans=Prim(n);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

并查集方法：

#include <cstdio>
    #include <cstring>
    
    int set[1001];
    
    int find(int x)
    {
        return set[x] < 0 ? x : set[x] = find(set[x]);
    }
    
    int main()
    {
        int n, m, a, b;
        while (scanf("%d", &n) != EOF && n)
        {
            scanf("%d", &m);
            memset(set, -1, sizeof set);
            while (m--)
            {
                scanf("%d%d", &a, &b);
                a = find(a);
                b = find(b);
                if (a != b)
                {
                    set[a] += set[b];
                    set[b] = a;
                }
            }
            int ans = -1;
            for (int i = 1; i <= n; ++i)
            {
                if (set[i] < 0)
                    ++ans;
            }
            printf("%d\n", ans);
        }
    }