poj3723-最大权森林

题目描述

需要招募女兵N人，男兵M人，每征募一个人需要花费10000元。但是如果男兵和女兵之间有亲密关系（亲密度为d）并且其中一人已经被征募时，征募另外一个人时费用可以减少d元，现在给出男兵和女兵之间的亲密度，题目要求是找出征募这些男兵女兵需要的最小费用。

题目分析

• 问题抽象

  • 将每个兵看作一个节点，如果利用了两个兵之间的亲密关系，就在表示这两个兵的节点之间连一条边，利用所有可能的关系后得到了一个图，题目要求图上边的权值之和最大。
  • 根据题目要求，得到的图不可能出现环路，因为至少有一个兵(第一个兵)被征募时没有利用关系，所以问题抽象成求图的最大权森林

• 问题解决

  Kruskal算法可以求解最小权森林的问题，我们可以将原图权值取反，将问题转化成求最小权森林的问题。

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);
    }
}