HDU.1233 还是畅通工程（Prim）

HDU.1233 还是畅通工程（Prim）

题意分析

1. 首先给出n，代表村庄的个数
2. 然后出n*(n-1)/2个信息，每个信息包括村庄的起点，终点，距离，
3. 要求求出最小生成树的权值之和。
4. 注意村庄的编号从1开始即可
5. 直接跑prim

代码总览

#include <bits/stdc++.h>

#define nmax 105

#define inf 1e8+7

using namespace std;

int mp[nmax][nmax];

int n;

int totaldis =0;

void prim()

{

    int lowcost[nmax];

    int path[nmax];

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

        lowcost[j] = mp[1][j];

        path[j] = 1;

    }

    path[1] = 0;

    int nowmin,nowminid;

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

        nowmin = inf;

        nowminid = 0;

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

            if(nowmin > lowcost[j] && lowcost[j] != 0){

                nowmin = lowcost[j];

                nowminid = j;

            }

        }

        totaldis += nowmin;

        lowcost[nowminid] = 0;

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

            if(mp[nowminid][j] < lowcost[j]){

                lowcost[j] = mp[nowminid][j];

                path[j] = nowminid;

            }

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

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

        int sta,end,dis;

        totaldis = 0;

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

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

                mp[i][j] = inf;

        for(int i = 1; i<=n*(n-1)/2 ;++i){

            scanf("%d %d %d",&sta,&end,&dis);

            mp[sta][end] = mp[end][sta] = dis;

        }

        prim();

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

    }

    return 0;

}