继续畅通工程（最小生成树） hdu ACM 1879 c++

柔光的暖阳◎ 2022-08-11 04:29 168阅读 0赞

# 继续畅通工程 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)**

Total Submission(s): 13981    Accepted Submission(s): 6080

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

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

思路：最小生成树，用模板就可以过的！！！！！！！

参考代码：

#include<cstdio>
    #include<cstring>
    int point[110][110],flag[110];
    int n,sum;
    
    void prim()
    {
         int i,j,k,v,min;
         flag[1]=1;
         sum=0;
         for(i=1;i<n;i++)
         {
             min=999999999;
             for(j=1;j<=n;j++)
                 if(flag[j])
                 {
                     for(k=1;k<=n;k++)
                         if(!flag[k]&& min > point[j][k])
                         {
                             min=point[j][k];
                             v=k;
                         }
                 }
             flag[v]=1;
             sum+=min;
         }
    }
    
    int main()
    {
        int i,j,m,a,b,p,temp;
        
        while(scanf("%d",&n),n)
        {
             memset(flag,0,sizeof(flag));
             m=(n*(n-1))/2;
             for(i=0;i<m;i++)
             {
                 scanf("%d%d%d%d",&a,&b,&p,&temp);
                 {
                     if(temp==1)
                         point[a][b]=point[b][a]=0;
                     else
                         point[a][b]=point[b][a]=p;    
                 }
             }
             prim();
             printf("%d\n",sum);
        }
        return 0;
    }