继续畅通工程-白红宇

继续畅通工程

阅读量：6938 次

发布时间：2019-06-27

本文共 1552 字，大约阅读时间需要 5 分钟。

题目描述：

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

输入：

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。

输出：

每个测试用例的输出占一行，输出全省畅通需要的最低成本。

样例输入：

31 2 1 01 3 2 02 3 4 031 2 1 01 3 2 02 3 4 131 2 1 01 3 2 12 3 4 10

样例输出：

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5 #include 
           
              6 #include 
            
              7 #include 
             
               8 #include 
              
                9 #include 
               
                 10 #include 
                
                  11 #include 
                 
                   12 #include 
                   13 #include 
                   
                     14 #include 
                    
                      15 #include 
                     
                       16 17 #define MAXD 99999999 18 using namespace std; 19 20 21 int fa[1000]; 22 23 struct Node{ 24 int v1,v2; 25 int cost; 26 }; 27 28 vector
                      
                       vt; 29 30 31 bool cmp(Node x,Node y) 32 { 33 if(x.cost
                       
                        0) 41 { 42 v=fa[v]; 43 } 44 return v; 45 } 46 47 48 49 50 51 52 53 int main() 54 { 55 56 57 int n,m; 58 59 int i,j,k; 60 61 while(scanf("%d",&n)!=EOF) 62 { 63 m=n*(n-1)/2; 64 65 if(n==0) 66 break; 67 68 int len=0; 69 vt.clear(); 70 71 72 73 74 75 for(i=0;i
                        
                         c) 97 vt[j].cost=c; 98 } 99 else100 {101 Node ans;102 ans.v1=a;103 ans.v2=b;104 ans.cost=c;105 vt.push_back(ans);106 len++;107 108 }109 }110 111 112 sort(vt.begin(),vt.end(),cmp);113 114 115 116 for(i=1;i<=n;i++)117 {fa[i]=0;}118 119 120 int num=0;121 int mincost=0;122 123 124 125 for(i=0;i

转载于:https://www.cnblogs.com/zjushuiping/archive/2012/05/30/2526842.html

你可能感兴趣的文章