題目描述

需要招募女兵N人，男兵M人，每征募一個人需要花費10000元欧穴。但是如果男兵和女兵之間有親密關(guān)系（親密度為d）并且其中一人已經(jīng)被征募時卦溢，征募另外一個人時費用可以減少d元糊余，現(xiàn)在給出男兵和女兵之間的親密度秀又，題目要求是找出征募這些男兵女兵需要的最小費用。

題目分析

• 問題抽象

  • 將每個兵看作一個節(jié)點啄刹，如果利用了兩個兵之間的親密關(guān)系涮坐，就在表示這兩個兵的節(jié)點之間連一條邊，利用所有可能的關(guān)系后得到了一個圖誓军，題目要求圖上邊的權(quán)值之和最大袱讹。
  • 根據(jù)題目要求，得到的圖不可能出現(xiàn)環(huán)路昵时，因為至少有一個兵(第一個兵)被征募時沒有利用關(guān)系捷雕，所以問題抽象成求圖的最大權(quán)森林

• 問題解決

  Kruskal算法可以求解最小權(quán)森林的問題，我們可以將原圖權(quán)值取反壹甥，將問題轉(zhuǎn)化成求最小權(quán)森林的問題救巷。

AC代碼

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_V = 20010;

struct Edge{
    int u;
    int v;
    int w;
    Edge(int u, int v, int w){
        this->u = u;
        this->v = v;
        this->w = w;
    }
    bool operator < (const Edge &e){
        return w < e.w;
    }
};

vector<Edge> edges; 
int N;
int M;
int R;
int res;

int p[MAX_V];
int r[MAX_V];

void init(){
    for(int i = 0; i < N + M; i++){
        p[i] = i;
        r[i] = 0;
    }
    edges.clear();
}

int Find(int x){
    if(x == p[x]) return x;
    else return p[x] = Find(p[x]);
}

void Union(int x, int y){
    int xRoot = Find(x);
    int yRoot = Find(y);
    if(xRoot < yRoot) p[xRoot] = yRoot;
    else {
        p[yRoot] = xRoot;
        r[xRoot]++;
    }
}

bool sameRoot(int x, int y){
    return Find(x) == Find(y);
}

void kruskal(){
    res = 0;
    sort(edges.begin(), edges.end());
    vector<Edge>::iterator it;
    for(it = edges.begin(); it != edges.end(); ++it){
        int u = (*it).u;
        int v = (*it).v;
        int w = (*it).w;
        if(!sameRoot(u, v)){
            Union(u, v);
            res += w;
        }
    }
}

int main(){
    int caseNum;
    scanf("%d", &caseNum);
    while(caseNum--){
        scanf("%d %d %d", &N, &M, &R);
        init();
        for(int i = 0; i < R; i++){
            int n, m, r;
            scanf("%d %d %d", &n, &m, &r);
            edges.push_back(Edge(n, N+m, -r));
        }
        kruskal();
        printf("%d\n", 10000 * (N + M) + res);
    }
}