学步园

贪心+并查集~~~

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define  inf 0x3f3f3f3f
#define  INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
const int MAXN = 10010;
const int MAXM = 100010;

struct Edge
{
    int u, v, w;
    Edge() {}
    Edge(int t_u, int t_v, int t_w) : u(t_u), v(t_v), w(t_w) {}
    bool operator < (const Edge &e) const
    {
        return w < e.w;
    }
}edge[MAXM];
int parent[MAXN], rank[MAXN], ncycle[MAXN];

void init_set()
{
    memset(parent, -1, sizeof(parent));
    memset(rank, 0, sizeof(rank));
    memset(ncycle, 0, sizeof(ncycle));
}

int find_set(int u)
{
    return parent[u] < 0 ? u : parent[u] = find_set(parent[u]);
}

void union_set(int r1, int r2, int w)
{
    if(parent[r2] < parent[r1])
    {
        parent[r2] += parent[r1];
        parent[r1] = r2;
        rank[r2] += rank[r1];
        rank[r2] += w;
        ncycle[r2] += ncycle[r1];
    }
    else
    {
        parent[r1] += parent[r2];
        parent[r2] = r1;
        rank[r1] += rank[r2];
        rank[r1] += w;
        ncycle[r1] += ncycle[r2];
    }
}


int main()
{
    //freopen("aa.in", "r", stdin);

    int n, m, r1, r2;

    while(scanf("%d %d", &n, &m) && n+m)
    {
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
        }
        sort(edge + 1, edge + m + 1);
        init_set();
        for(int i = m; i >= 1; --i)
        {
            r1 = find_set(edge[i].u);
            r2 = find_set(edge[i].v);
            if(r1 != r2 && ncycle[r1] + ncycle[r2] <= 1)
            {
                union_set(r1, r2, edge[i].w);
            }
            else
            {
                if(ncycle[r1] == 0)
                    rank[r1] += edge[i].w, ncycle[r1]++;
            }
        }
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            if(parent[i] < 0)
                ans += rank[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}