hdu1102 Constructing Roads prim最小生成树

There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.

We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.

Input

The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.

Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.

Output

You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.

Sample Input

3
0 990 692
990 0 179
692 179 0
1
1 2

Sample Output

179
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x1f1f1f1f    //定义一个整数常量,表示无穷大
// prim函数返回得到的最小生成树的n-1条边的权值和
// 参数cost 为表示图的矩阵,n为顶点个数
int prim(int cost[][100],int n)
{
    //low表示每个点到生成树的最小距离,vis表示一个点是否已经加入生成树中
    int low[10000];
    int vis[10000]={0};        //顶点数n<10000 
    int i,j,p;
    int min,res=0;                        //res表示最小生成树权值和 
    vis[0]=1;                            //将第一个顶点加入集合S 
    for(int i=1;i<n;++i)                //并更新该顶点到其他顶点的距离 
    {
        low[i] = cost[0][i];
    }
    for(int i=1;i<n;++i)                //尝试加入剩下的n-1条边 
    {
        min = INF;                        //寻找点集V-S中距离集合S最近的距离的点 
        p=-1;                            //min为权值,p为位置 
        for(int j=0;j<n;++j)
        {
            if(0==vis[j] && min>low[j])
            {
                min = low[j];
                p = j;
            }
        }    
        //min==INF 说明找不到能够加入的点了,说明图是不连通的(已经加入的点集和未加入的点集不连通)。
        if(min==INF) return -1;
        
        res+=min;
        vis[p]=1;        //P点加入生成树的点集 
        
        for(j=0;j<n;++j)    //加入该点后更新集合S到集合V-S之间的距离 
        {
            if(vis[j]==0 && low[j]>cost[p][j])
            {
                low[j] = cost[p][j];    
            }    
        } 
    }
    return res;    
} 
int main()
{
    int a[100][100];
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                cin>>a[i][j];    
            }    
        }    
        int t,x,y;
        cin>>t;
        while(t--)
        {
            cin>>x>>y;
            a[x-1][y-1]=a[y-1][x-1]=0;
        }
        int ans = prim(a,n);
        cout<<ans<<endl;
    }
    return 0;    
} 
Last modification:January 12th, 2020 at 04:21 am
如果觉得我的文章对你有用,请随意赞赏