把路按时间排序,加权size[i]表示 i 所属的并查集的个数 按顺序依次合并每条路 每次合并完判断当前并查集的size是否达到n
|
|
|
|
|
|
十五分钟搞定,复习kruscal
|
|
prim也能过的说!!!
题目 1109 [福州培训2010] 修复公路
2017-11-13 15:38:49
|
|
并查集的基础练习
|
|
看错题。。
|
|
最小生成树的最大边一定是所有生成树中最小的。
因为kruskal算法保证在取到这条边之前构不成生成树
题目 1109 [福州培训2010] 修复公路
2016-08-15 22:56:32
|
|
#include<iostream>
#include<cstdio> #include<cstring> using namespace std; const int maxn=1000; struct Node{ int from,to,cost; }a[100001]; bool comp(const Node &a,const Node &b){ return a.cost<b.cost; } int n,m,root[1001]; void Kruskal(); int Findroot(int); int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z;cin>>x>>y>>z; a[i].from=x;a[i].to=t;a[i].cost=z; } Kruskal(); return 0; } void Kruskal(){ int ans=0,cnt=0; for(int i=1;i<=n;i++){ root[i]=i; } sort(a+1,a+m+1,comp); for(int i=1;i<=m;i++){ int x=a[i].from,y=a[i].to; int rx=Findroot(x),ry=Findroot(y); if(rx==ry) continue; else{ root[rx]=ry;cnt++; if(a[i].cost>ans) ans=a[i].cost; } if(cnt==n-1) break; } if } int Findroot(int x){ if(x!=root[x]){ root[x]=Findroot(root[x]); } return root[x]; }
题目 1109 [福州培训2010] 修复公路
2016-02-26 11:11:20
|
|
用Kruskal求最小生成树即可
|
|
|
|
Kruskal+cnt计数,如果循环到最后都没有 cnt = n -1 ;说明没有连通
输出-1,其他的就是个裸的最小生成树 |
|
居然把m打成了n
|
|
|
|
|
|
连MST都不会写了。。。
刷水太少了。。。。。。
题目 1109 [福州培训2010] 修复公路
2013-10-21 20:42:05
|
|
奇葩地跪在0~n-1和1~n的问题上了……
|