D - 继续畅通工程

男娘i 2022-03-19 10:10 175阅读 0赞

### 题目描述： ###

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。  
Input  
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。  
Output  
每个测试用例的输出占一行，输出全省畅通需要的最低成本。  
Sample Input  
3  
1 2 1 0  
1 3 2 0  
2 3 4 0  
3  
1 2 1 0  
1 3 2 0  
2 3 4 1  
3  
1 2 1 0  
1 3 2 1  
2 3 4 1  
0  
Sample Output  
3  
1  
0

##### 分析： #####

本题的话也是一个最小生成树。只是要将输入的数据转化成邻接矩阵。然后同时需要注意那两个城镇之间是否有道路连接。如果有道路连接的话，那我们可以将其两个城镇之间的修路成本置为0。这样的话，就是一个模板题目了。只不过在实际操作做，我们需要将邻接矩阵里面i==j的位置置位-1。  
AC代码：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
      using namespace std;
    #define INF 1000000
    void MinSpanTree(int Graph[][5000],int N)
    {
        int i,j,k;
        int vexs[5000];
        int weight[5000];
        int sum=0;
        for(i=0;i<N;i++)
        {
            vexs[i]=i;
            weight[i]=Graph[0][i];
        }
        for(i=0;i<N-1;i++)
        {
            int Min=INF;
            j=0;k=0;
            while(j<N)
            {//这里与模板有所区别 
                if(weight[j]!=-1&&Min>weight[j])
                {
                    k=j;
                    Min=weight[j];
                }
                j++;
            }
            sum+=Min;
            weight[k]=-1;
            for(j=0;j<N;j++)
            {
                if(weight[j]!=-1&&weight[j]>Graph[k][j])
                {
                    vexs[j]=k;
                    weight[j]=Graph[k][j];
                }
            }
        }
      printf("%d\n",sum);
    
    }
    int Graph[5000][5000];
    int main()
    {
        int N;
        int x,y,fear,mark;
        while(~scanf("%d",&N))
        {
            if(N==0)
                break;
            for(int i=0;i<N*(N-1)/2;i++)
            {
                scanf("%d%d%d%d",&x,&y,&fear,&mark);
                if(mark==1)
                    fear=0;
                x--;y--;//因为下标是从0开始的。
                Graph[x][y]=fear;
                Graph[y][x]=fear;
    
            }
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<N;j++)
                     if(i==j)//需要将下标相同的位置置为-1。
                        Graph[i][j]=-1;
            }
    
            MinSpanTree(Graph,N);
        }
    }