Destroy Walls HDU - 6187(最大生成树)

本文主要是介绍Destroy Walls HDU - 6187(最大生成树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：现有一个图，一个人在图中某一点，要使此人能够达到任意位置，需要拆掉的边最少且付费代价最少是多少；

思路：如果想到达任意位置，那么图中一定无环，首先想到的是拓扑排序判环，然后将每个环中的最小边去掉，但是这样太复杂了，，，换个方向，，，图中无环不就是全是树嘛！要求代价最小，那么构造一个最大生成树（森林）就OK了 ；

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n, m;
struct node{int u, v, w;bool operator <(const node &a) const{return w>a.w;}
}edge[maxn];
int pre[maxn];
int Find(int x){return pre[x]==x?pre[x]:pre[x]=Find(pre[x]);
}
bool Union(int x, int y){int fx=Find(x);int fy=Find(y);if(fx==fy) return false;pre[fy]=fx;return true;
}
void init(){for(int i=0; i<=n; i++){pre[i]=i;}
}
int main(){while(~scanf("%d%d", &n, &m)){int x, y;init();for(int i=0; i<n; i++){scanf("%d%d", &x, &y);}long long sum=0;for(int i=0; i<m; i++){scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);sum+=edge[i].w;}sort(edge, edge+m);int e_cnt=0;long long w_sum=0;for(int i=0; i<m; i++){if(Union(edge[i].u, edge[i].v)){e_cnt++;w_sum+=edge[i].w;}}int e_ans=m-e_cnt;long long w_ans=sum-w_sum;printf("%d %lld\n", e_ans, w_ans);}return 0;
}

这篇关于Destroy Walls HDU - 6187(最大生成树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---