Descrição

O governante Windy deseja formar um exército. Ele pode recrutar N mulheres e M homens, pagando 10.000 RMB por cada soldado sem vantagens especiais. Existem relações entre alguns pares de mulher-homem. Se uma relação com desconto d existir e um dos endivíduos já estiver recrutado, o outro pode ser recrutado por 10.000 - d RMB. Cada relação pode ser usada apeenas uma vez. O objetivo é calcular o custo mínimo total para recrutar todos os N+M indivíduos.

Entrada

A primeira linha contém o número de casos de teste. Cada caso de teste inicia com três inteiros N, M e R, seguidos por R linhas contendo os inteiros xi, yi e di, representando uma relação entre a mulher xi e o homem yi com desconto di.

• 1 ≤ N, M ≤ 10000
• 0 ≤ R ≤ 50000
• 0 ≤ xi < N
• 0 ≤ yi < M
• 0 < di < 10000

Saída

Para cada caso de teste, imprima o custo mínimo total em uma linha.

Exemplo de Entrada

2

5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781

5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889

Exemplo de Saída

71071
54223

Solução

O problema pode ser modelado como um grafo bipartido onde cada indivíduo é um nó e cada relação é uma aresta com peso di. Para minimizar o custo total, devemos maximizar a soma dos descontos utilizados. Isso equivale a encontrar uma árvore geradora máxima no grafo. Podemos transformar isso em um problema de árvore geradora mínima atribuindo peso negativo (-di) a cada aresta e aplicando o algoritmo de Kruskal. O custo final é calculado como 10000*(N+M) + custo_da_árvore_geradora_mínima.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int MAXIMO = 100000;
int pai[MAXIMO], altura[MAXIMO];

void inicializar(int total) {
    for (int i = 0; i < total; ++i) {
        pai[i] = i;
        altura[i] = 0;
    }
}

int encontrar(int vertice) {
    if (pai[vertice] == vertice) return vertice;
    return pai[vertice] = encontrar(pai[vertice]);
}

void fundir(int a, int b) {
    a = encontrar(a);
    b = encontrar(b);
    if (a == b) return;
    if (altura[a] < altura[b]) {
        pai[a] = b;
    } else {
        pai[b] = a;
        if (altura[a] == altura[b]) ++altura[a];
    }
}

struct Aresta {
    int origem, destino, peso;
    bool operator<(const Aresta& outra) const {
        return peso < outra.peso;
    }
};

int kruskal(int vertices, vector<Aresta>& arestas) {
    sort(arestas.begin(), arestas.end());
    inicializar(vertices);
    int custo_total = 0;
    for (const auto& aresta : arestas) {
        if (encontrar(aresta.origem) != encontrar(aresta.destino)) {
            fundir(aresta.origem, aresta.destino);
            custo_total += aresta.peso;
        }
    }
    return custo_total;
}

int main() {
    int casos;
    cin >> casos;
    while (casos--) {
        int mulheres, homens, relacoes;
        cin >> mulheres >> homens >> relacoes;
        vector<Aresta> lista_arestas;
        for (int i = 0; i < relacoes; ++i) {
            int m, h, desconto;
            cin >> m >> h >> desconto;
            lista_arestas.push_back({m, mulheres + h, -desconto});
        }
        int total_vertices = mulheres + homens;
        int custo_mst = kruskal(total_vertices, lista_arestas);
        cout << 10000 * total_vertices + custo_mst << endl;
    }
    return 0;
}