无向图最小生成树

爱被打了一巴掌 2022-06-12 06:42 189阅读 0赞

N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。

Input

第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)   
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)

Output

输出最小生成树的所有边的权值之和。

Sample Input

9 14
    1 2 4
    2 3 8
    3 4 7
    4 5 9
    5 6 10
    6 7 2
    7 8 1
    8 9 7
    2 8 11
    3 9 2
    7 9 6
    3 6 4
    4 6 14
    1 8 8

Sample Output

利用并查集加贪心来写

#include<cstdio>
    #include<algorithm>
    using namespace std;
    int f[1001],sum,num;
    struct A{
        int s,e,w;
    }g[50000];
    bool cmp(A a,A b)
    {
        return a.w<b.w;
    }
    int find(int x)
    {
        return f[x]==x?x:f[x]=find(f[x]);
    }
    void merge(int x,int y,int z)
    {
        x=find(x);
        y=find(y);
        if(x!=y)
        {
            num++;
            sum+=z;
            f[x]=y;
        }
    }
    int main()
    {
        int n,m;
        while(~scanf("%d %d",&n,&m))
        {
            for(int i=1;i<=n;i++)
                f[i]=i;
            sum=num=0;
            for(int i=0;i<m;i++)
                scanf("%d %d %d",&g[i].s,&g[i].e,&g[i].w);
            sort(g,g+m,cmp);
            for(int i=0;i<m&&num<n-1;i++)
                 merge(g[i].s,g[i].e,g[i].w);
            printf("%d\n",sum);
        }
        return 0;
    } dijkstra算法：
     #include<cstdio>
    #include<cstring>
    #define N 1001
    #define M 99999999
    int num[N];
    int n,m;
    int tt,sum;
    int map[N][N];
    int p[N];
    void dijkstra()
    {
        int i,j;
        memset(p,0,sizeof(p));
        for(i=1;i<=n;i++)
            num[i] = map[1][i];
        p[1]=1;
        for(i=1; i<n; i++)
        {
            int min = M,k;
            for(j=1; j<=n; j++)
            {
                if(p[j] == 0 && num[j]<min)
                {
                    min = num[j];
                    k=j;
                }
            }
            tt = tt + min;
            p[k] = 1;
            for(j=1; j<=n; j++)
            {
                if(p[j]==0 && num[j]>map[k][j])
                {
                    num[j] = map[k][j];
                }
            }
        }
        printf("%d\n",tt);
    }
    int main()
    {
        int T,i,j;
        int a[1001];
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            tt = 0;
            for(i=1; i<=n; i++)
            {
                for(int j=1; j<=n; j++)
                    map[i][j] = M;
                map[i][i] = 0;
            }
            int x,y,z;
            for(i=0; i<m; i++)
            {
                scanf("%d%d%d",&x,&y,&z);
                map[x][y] = z;
                map[y][x] = z;
            }
            dijkstra();
        }
        return 0;
    }