九度oj 题目1028：继续畅通工程

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

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

当N为0时输入结束。

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

样例输入：

样例输出：

3

1

0

该题在1024题的基础上略微修改即可，已修的路价格为0，未修的路价格为原价
代码如下：

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #define MAX 102

 #define inf 0x3f3f3f3f

 int flag[MAX];

 int cost[MAX][MAX];

 int lowCost[MAX];

 int main(int argc, char const *argv[])

 {

     int n,m;

     scanf("%d",&n);

     while(n != ) {

         int count = ;

         m = n * (n-)/;

         for(int i = ; i <= n; i++) {

             flag[i] = ;

             for(int j = ; j <= n; j++) {

                 cost[i][j] = inf;

             }

         }

         for(int i = ; i < m; i++) {

             int a,b,c,d;

             scanf("%d %d %d %d",&a,&b,&c,&d);

             if(d == ) {

                 cost[a][b]= cost[b][a] = c;

             }

             else {

                 cost[a][b]= cost[b][a] = ;

             }

         }

             int sumCost = ;

             for(int i = ; i <= n; i++) {

                 lowCost[i] = cost[][i];

             }

             flag[] = ;

             for(int i = ; i <= n; i++) {

                 int min = inf;

                 int v = -;

                 for(int i = ; i <= n; i++) {

                     if(flag[i] ==  && lowCost[i] < min) {

                         min = lowCost[i];

                         v = i;

                     }

                 }

                 flag[v] = ;

                 sumCost = sumCost + lowCost[v];

                 for(int i = ; i <= n; i++) {

                     if(cost[v][i] < lowCost[i]) {

                         lowCost[i] = cost[v][i];

                     }

                 }

             }

             printf("%d\n",sumCost);

         scanf("%d",&n);

     }

     return ;

 }

巴特西

九度oj 题目1028：继续畅通工程

最新文章

热门文章