首页 > 代码库 > hdu 1863 通畅工程

hdu 1863 通畅工程

2024-07-16 15:54:53   219人阅读

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
?

最小生成树 Kruskal

#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffff#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;struct Road{    int f,t;    int w;};Road r[10005];int vil[1200],n,m,sum,ans;int cmp(Road a,Road b){    return a.w<b.w;}int find(int a){    return vil[a]==a?a:find(vil[a]);}void Kruskal(){    for(int i=1;i<=m;i++) vil[i]=i;//对并查集初始化    sort(r+1,r+n+1,cmp);    for(int i=1;i<=n;i++)    {       int x=find(r[i].f),y=find(r[i].t);       if(x!=y)       {           sum++;           vil[y]=x;           ans+=r[i].w;       }    }    if(sum==m)    {        printf("%d\n",ans);    }    else    {        printf("?\n");    }}int main(){    int i,j;    int u,v,ww;    while(scanf("%d%d",&n,&m)!=EOF)    {        if(n==0) break;        sum=1;ans=0;        for(i=1;i<=n;i++)        {            scanf("%d%d%d",&u,&v,&ww);            r[i].f=u;            r[i].t=v;            r[i].w=ww;        }        Kruskal();    }    return 0;}

　　


联系
我们