題目描述

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

題目分析

• 問(wèn)題抽象

  • 將每個(gè)兵看作一個(gè)節(jié)點(diǎn)，如果利用了兩個(gè)兵之間的親密關(guān)系，就在表示這兩個(gè)兵的節(jié)點(diǎn)之間連一條邊，利用所有可能的關(guān)系后得到了一個(gè)圖，題目要求圖上邊的權(quán)值之和最大。
  • 根據(jù)題目要求，得到的圖不可能出現(xiàn)環(huán)路，因?yàn)橹辽儆幸粋€(gè)兵(第一個(gè)兵)被征募時(shí)沒(méi)有利用關(guān)系，所以問(wèn)題抽象成求圖的最大權(quán)森林

• 問(wèn)題解決

  Kruskal算法可以求解最小權(quán)森林的問(wèn)題，我們可以將原圖權(quán)值取反，將問(wèn)題轉(zhuǎn)化成求最小權(quán)森林的問(wè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);
    }
}