襄阳网站建设八零后,做的网站怎么上传到网上运行,网站开发开源软件,贸易公司如何做英文网站市政府“惠民工程”的目标是在全市 n 个居民点间之架设煤气管道#xff08;但不一定有直接的管道相连#xff0c;只要能间接通过管道可达即可#xff09;。很显然最多可架设 n(n−1)/2 条管道#xff0c;然而实际上要连通 n 个居民点只需架设 n−1 条管道就可以了。现请你编…市政府“惠民工程”的目标是在全市 n 个居民点间之架设煤气管道但不一定有直接的管道相连只要能间接通过管道可达即可。很显然最多可架设 n(n−1)/2 条管道然而实际上要连通 n 个居民点只需架设 n−1 条管道就可以了。现请你编写程序计算出该惠民工程需要的最低成本。
输入格式 输入包含多组测试数据。每组数据第一行包含两个整数 n 和 m表示居民点数量和评估管道数量。接下来 m 行每行包含三个整数 a,b,c表示居民点 a 和 b 之间架设管道需要 c的成本。居民点编号 1∼n。
输出格式 每组数据输出一行一个结果表示全市管道畅通所需要的最低成本。若统计数据不足以保证畅通则输出 ?。
数据范围 2≤n≤100, 1≤m≤n(n−1)2, 1≤a,b≤n, 1≤c≤100, 每个输入最多包含 100 组数据。
输入样例 3 3 1 2 1 1 3 2 2 3 4 3 1 2 3 2
输出样例 3 ?
#includeiostream
#includealgorithm
using namespace std;
const int N110,MN*(N-1)/2;
int n,m,fa[N];
struct edge{int a,b,c;
}e[M];
bool cmp(edge x,edge y)
{return x.cy.c;
}
int find(int x)
{if(x!fa[x]) fa[x]find(fa[x]);return fa[x];
}
int main()
{while(cinnm){for(int i0;im;i){int a,b,c;cinabc;e[i].aa,e[i].bb,e[i].cc;}for(int i1;in;i) fa[i]i;sort(e,em,cmp);int cntn,res0;for(int i0;im;i){int xe[i].a,ye[i].b,ze[i].c;if(find(x)find(y)) continue;fa[find(x)]find(y);cnt--,resz;}if(cnt1) coutresendl;else cout?endl;}return 0;
}
