HDU 1102 最小生成树裸题，kruskal，prim

1、HDU  1102  Constructing Roads    最小生成树

2、总结：

题意：修路，裸题

(1)kruskal

//kruskal

#include<iostream>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

#include<cstdio>

#define max(a,b) a>b?a:b

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

const int N=;

int n,k;

int father[N];

struct Eage

{

    int st,en,val;

}eage[N*(N+)/];

bool cmp(Eage a,Eage b)

{

    return a.val<b.val;

}

int findn(int x)   //即并查集的查找

{

    int t=x;

    while(x!=father[x]){

        x=father[x];

    }

    int p;

    while(t!=x){

        p=t;

        t=father[t];

        father[p]=x;

    }

    return x;

}

int kruskal()

{

    int sum=;

    sort(eage,eage+k,cmp);

    for(int i=;i<k;i++){

        int x=findn(eage[i].st);

        int y=findn(eage[i].en);

        if(x!=y){

            sum+=eage[i].val;

            x=findn(x);

            y=findn(y);

            father[x]=y;

        }

    }

    return sum;

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        int m;

        k=;

        for(int i=;i<=n;i++){

            for(int j=;j<=n;j++){

                scanf("%d",&m);

                if(i<j){

                    eage[k].st=i;   //st边起点，en边终点，k为边的条数

                    eage[k].en=j;

                    eage[k++].val=m;

                }

            }

        }

        for(int i=;i<=n;i++){

            father[i]=i;

        }

        int q,a,b;

        scanf("%d",&q);

        while(q--){

            scanf("%d%d",&a,&b);

            a=findn(a);

            b=findn(b);

            father[a]=findn(b);  //把a与b连通

        }

        int ans=kruskal();

        printf("%d\n",ans);

    }

    return ;

}

(2)prim

//prim

#include<iostream>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

#include<cstdio>

#define max(a,b) a>b?a:b

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

const int N=;

int n;

int mapn[N][N];

int visit[N],dis[N];   //dis存储每个点到所选结点的最短距离

int prim()

{

    int sum=;

    memset(visit,,sizeof(visit));

    visit[]=;

    for(int i=;i<=n;i++){  //先选第一个结点

        dis[i]=mapn[][i];

    }

    for(int i=;i<n;i++)    //注，<不是<=

    {

        int next,minn=INF;

        for(int j=;j<=n;j++){  //找到下一个最近的结点

            if(!visit[j]&&minn>dis[j]){

                next=j;

                minn=dis[j];

            }

        }

        sum+=minn;

        visit[next]=;

        for(int j=;j<=n;j++){  //更新dis

            if(!visit[j]&&dis[j]>mapn[next][j]){

                dis[j]=mapn[next][j];

            }

        }

    }

    return sum;

}

int main()

{

    int q,a,b;

    while(scanf("%d",&n)!=EOF)

    {

        memset(mapn,INF,sizeof(mapn));

        for(int i=;i<=n;i++){

            for(int j=;j<=n;j++){

                scanf("%d",&mapn[i][j]);

            }

        }

        scanf("%d",&q);

        while(q--){

            scanf("%d%d",&a,&b);

            mapn[a][b]=mapn[b][a]=;

        }

        int ans=prim();

        printf("%d\n",ans);

    }

    return ;

}