题意是说求伪森林的边权之和最大。伪森林的定义是:每一个连通分量允许至多有一个环。
这题本质上和kruskal差不多,但是要注意:
因为要和最大,所以排序的时候从大到小。
排序后枚举每一条边,判断它的两个端点:
1.两个端点属于同一个集合。如果这个集合还没有环,那么就加上这条边并标记次集合有环
2.两个端点属于不同的集合。如果这两个集合至多只有一个集合有环的话,那么就可以加上这条边合并这两个集合,一定记得要修改合并后集合的环标志。
#include <iostream> #include<stdio.h> #include<algorithm> #define maxn 100010 using namespace std; int n,m; typedef struct edge { int u,v,w; } Edge; Edge e[maxn]; int fa[maxn]; int loop[maxn]; //当前并查集是否有环 int cmp(const void *a,const void *b) { Edge* aa = (Edge*)a; Edge* bb = (Edge*)b; return bb->w - aa->w; } int find(int a) { return fa[a] == a?a:fa[a] = find(fa[a]); } int main() { while(true) { scanf("%d %d",&n,&m); if(n+m == 0) break; for(int i = 0; i < n; i++) { fa[i] = i; loop[i] = 0; } for(int i = 0; i < m; i++) { scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w); } qsort(e,m,sizeof (Edge),cmp); int ans = 0; for(int i = 0 ; i < m; i++) { int u = e[i].u; int v = e[i].v; int w = e[i].w; int fa_u = find(u); int fa_v = find(v); if(fa_u == fa_v ) //属于同一个集合 { if(!loop[fa_u]) //如果这个集合还没有环 { loop[fa_u] = 1; ans+=w; } } else { if(loop[fa_u] + loop[fa_v] < 2) //两个连通分量至多一个环 { fa[fa_v] = fa_u; loop[fa_u] += loop[fa_v]; //改变环标记,父节点的环标记为两个集合的环数目的和 ans+=w; } } } printf("%d\n",ans); } return 0; }