Vegetable and Road again [最小生成树]

2019-11-06 06:23:06

字体：大中小

来源：转载

供稿：网友

修路的方案终于确定了。市政府要求任意两个公园之间都必须实现公路交通（并不一定有直接公路连接，间接公路相连也可以）。但是考虑到经济成本，市政府希望钱花的越少越好。

你能帮助Vegetable找到给出的修路方案所需的最少花费吗？

输入有T组测试数据。

每组包含一组N(0

#include<cstdio>#include<algorithm>using namespace std;#define maxn 110int par[maxn],rak[maxn];void set_init(){ for (int i = 0; i < maxn; ++i){ par[i] = i; rak[i] = 0; }}int set_find(int x){ return x == par[x]? x : par[x] = set_find(par[x]);}void set_union(int x,int y){ int tx = set_find(x); int ty = set_find(y); if (tx == ty) return ; if (rak[tx] > rak[ty]) par[tx] = ty; else{ par[ty] = tx; if (rak[tx] == rak[ty]) rak[tx]++; }}struct node { int from,to,cost;}spot[maxn];bool cmp(node a,node b){ if (a.cost!=b.cost) return a.cost < b.cost;}int main(){ int t; scanf("%d",&t); while (t--){ int n,m; scanf("%d%d",&n,&m); set_init(); for (int i = 0; i < m; ++i) scanf("%d%d%d",&spot[i].from,&spot[i].to,&spot[i].cost); sort(spot,spot+m,cmp); int res = 0; for (int i = 0; i < m; ++i){ int vf = spot[i].from; int vt = spot[i].to; if (set_find(vf) != set_find(vt)){ set_union(vf,vt); res += spot[i].cost; } } int fg = 0; for (int i = 2; i <= n; ++i){ if (set_find(i) != set_find(1)){ fg = 1; break; } } if (fg) PRintf("Wrong/n"); else printf("%d/n",res); } return 0;}

这题血亏又是在判断森林的地方出错了如果做出来积分赛好歹也能进前九总的来说这次竞赛状态极差竟然一直对着绑定的两个节点搜索判断现在想想怎么可能判断得出这题坐标点仍然是1到n 思考如果不是1到n 而是任意给的点想法标记已出现的点判断时搜索这些点如果有重边想法在把两个节点并起来的时候判断是否已经在同一个跟节点上

多做点题吧…

上一篇：学习Maven之Properties Maven Plugin

下一篇：HANA STUDIO常用快捷键