首页 > 代码库 > HDoj-1863-畅通工程-并查集

HDoj-1863-畅通工程-并查集

2024-07-26 23:59:53   221人阅读

畅通工程
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 17006    Accepted Submission(s): 7140




Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，
只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。
现请你编写程序，计算出全省畅通需要的最低成本。


Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N 
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。
为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。


Output
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。


Sample Input
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
 


Sample Output
3

?

#include <stdio.h> 
#include<string.h>
#include <algorithm>
using namespace std;
struct Road
{
    int c1, c2, cost;
};
Road road[110];

bool cmp(Road a,Road b)
{
    return a.cost<b.cost;
}
int city[110];

int find(int a)
{
    int r=a;
    while(city[r]!=r)
       r=city[r];
    return r;
}
bool merge(int x, int y)
{
    int fx,fy;
     fx = find(x);
     fy = find(y);
    if(fx == fy)   return 0;
    else if(fx < fy)
           city[fy] = fx;
    else
           city[fx] = fy;
return 1;
} 

int main()
{
    int n, m;                         
    while(scanf("%d %d", &m, &n) && m)
    {
        int i;
        for(i=1;i<=n;i++) 
        {
            city[i]=i;
        }
        for(int i=0; i<m; ++i)
            scanf("%d %d %d", &road[i].c1, &road[i].c2, &road[i].cost);
        sort(road, road+m,cmp);
        int sum = 0, count = 0;
        for(int i=0; i<m; i++)
        {
            if(merge(road[i].c1, road[i].c2))
            {
                count ++;
                sum += road[i].cost;
            }
            if(count == n-1)
                break;
        }
        if(count == n-1)
            printf("%d\n", sum);
        else
            printf("?\n");
    }
    return 0;
}


HDoj-1863-畅通工程-并查集


联系
我们