HDU - 1102-Constructing Roads——最小生成树prim

谁践踏了优雅 2022-06-07 12:26 132阅读 0赞

# Constructing Roads #

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

大概是我英文太差，这道题刚开始都没看出来是多组数据。我还奇怪呢，果然没有多组数据就wa了555555.。。。

题意：题意还用我说吗，我英语这么差还能看懂大概意思。就是有几个小村庄，要修路，不是任意两个都要直接相连，间接相连也行。

原本已经有了几个修好的路，问现在要完善使所有小村庄相连的做小花费

输入是一个n\*n的数组

把已经修好的路的花费为0就行了。

#include <bits/stdc++.h>///这才是prim模板，之前的模板真坑。Constructing Roads
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXV 105
    int Tu[MAXV][MAXV];
    int bj[MAXV];//标记这个点有没有访问过
    int N,M,S,T,Q,minn;
    void prim()
    {
        int lowcost[MAXV];///保存权值，用来查找最小。已经查过使值等于0
        //int closet[MAXV];///保存路。
        int i,j,k;
        for(i=1;i<=N;i++)///初始化距离起点的值lowcost
        {
            lowcost[i]=Tu[1][i];//起点为1
            bj[i]=0;
            //closet[i]=1;//保存起点
        }
        bj[1]=1;
        k=1;
        for(i=2;i<=N;i++)///遍历除起点外所有的点
        {
            int minds=INF;
            for(j=1;j<=N;j++)///找到距离最近的值
            {
                if(bj[j]==0&&lowcost[j]<minds)///找到要新加入点k
                {
                    minds=lowcost[j];
                    k=j;
                }
            }
            if(minds==INF)return;
            bj[k]=1;
            lowcost[k]=0;///已经查过使值等于0
            minn+=minds;///路程和
            //printf("满足条件的边(%d,%d),权值为%d\n",closet[k],k,minds);
            for(j=1;j<=N;j++)///更新lowcost
            {
                if(bj[j]==0&&Tu[k][j]<lowcost[j])///根据新加入的k，查找是否有距离更近的值。
                {
                    lowcost[j]=Tu[k][j];
                    //closet[j]=k;///将点保存
                }
            }
        }
    }
    int main()
    {
        while(scanf("%d",&N)!=EOF)
        {
        //init();
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
        {
            scanf("%d",&Tu[i][j]);
        }
        scanf("%d",&Q);
        while(Q--)
        {
            scanf("%d %d",&S,&T);
            Tu[S][T]=Tu[T][S]=0;
        }
        minn=0;
        prim();
        printf("%d\n",minn);
        }
        return 0;
    }