每个连通分量最多只有一个环，求怎么连接使费用最大
按费用从大到小排序，一条一条加边，连接一个集合内两个点的时候，判断这个集合之前有没有成环，连接两个集合的时候，判断两个集合的状态，如果都没有，则合并后也没有环，如果有一个有环，合并有也有环，如果两个都有环，则不能合并。
#include#include #include #include using namespace std;int father[100010], g[100010], ff[100010], bb[100010];struct abc{ int start, end, cost; }node[100010];bool cmp(const abc&a, const abc&b){ return a.cost > b.cost; }int find(int x){ if (x != father[x]) father[x] = find(father[x]); return father[x];}int main(){ int n, m, i, j, u, v, c, t; while (~scanf("%d%d", &n, &m)) { if (n == 0 && m == 0) break; int tot = 0; memset(ff, 0, sizeof(ff)); memset(bb, 0, sizeof(bb)); for (i = 0; i <= n; i++) father[i] = i; for (i = 1; i <= m; i++) { scanf("%d%d%d", &u, &v, &c); node[tot].start = u; node[tot].end = v; node[tot].cost = c; tot++; } sort(node, node + tot, cmp); int ans = 0; for (i = 0; i < tot; i++) { int x = find(node[i].start); int y = find(node[i].end); if (x == y) { if (bb[x] == 0) { bb[x] = 1; ans = ans + node[i].cost; } } else if (x != y) { if (bb[x] == 0&&bb[y]==0) { father[y] = x; ans = ans + node[i].cost; } else if (bb[x] == 0&&bb[y]==1) { bb[x] = 1; father[y] = x; ans = ans + node[i].cost; } else if (bb[x] == 1 && bb[y] == 0) { bb[y] = 1; father[x] = y; ans = ans + node[i].cost; } } } printf("%d\n", ans); } return 0;}