poj3723

最小生成树，稀疏图用kruskal，O（ElogE）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

#define maxr 50005
#define maxn 20005

struct Edge
{
    int u, v, w;
} edge[maxr];

int father[maxn];
int n, m, r;
int ans;

bool operator < (const Edge &a, const Edge &b)
{
    return a.w > b.w;
}

int getanc(int a)
{
    if (father[a] == a)
        return a;
    return father[a] = getanc(father[a]);
}

void merge(int a, int b)
{
    father[getanc(a)] = getanc(b);
}

void input()
{
    scanf("%d%d%d", &n, &m, &r);
    for (int i = 0; i < r; i++)
    {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
        edge[i].v += n;
    }
}

void work()
{
    ans = 0;
    for (int i = 0; i < n + m; i++)
        father[i] = i;
    for (int i = 0; i < r; i++)
    {
        if (getanc(edge[i].u) == getanc(edge[i].v))
            continue;
        merge(edge[i].u, edge[i].v);
        ans += edge[i].w;
    }
    printf("%d\n", (n + m) * 10000 - ans);
}

int main()
{
    //freopen("t.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while (t--)
    {
        input();
        sort(edge, edge + r);
        work();
    }
    return 0;
}