【POJ】Conscription

POJの問題

3723 -- Conscription

参考書

プログラミングコンテストチャレンジブック [第2版]
今回の解法はこの本から得ています.

難しさ（初心者目線）

・考え方****

・実装****

・面白さ*****

問題概要

・女N人、男M人を雇いたい
・1人10000ドルで雇える・ただし、女と男の間に親密な関係がある場合がある
・親密な関係は親密度Zで表される
・親密な場合はすでに片方が雇われていたらもう片方は(10000-Z)ドルで雇える
・雇う順番は自由である
・(N+M)人を雇うのにかかる最小のお金を求めよ

方針

・無向グラフで考える
・男と女の番号を頂点とする(男と女共に0から始まるので男は+Nしておく)
・男Aと女Bが親密な関係の場合頂点Aと頂点Bを結ぶ(costは-1*親密度にしておく)
・閉路ができないように辺を小さいコストから選んで行く->最小全域木->クラスカル法

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define pb         push_back
#define mp         make_pair
#define ll         long long
#define PI         acos(-1.0)
#define ALL(A)     ((A).begin(), (A).end())
#define vsort(v)   sort(v.begin(),v.end())
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//無向グラフで考える
//男と女の番号を頂点とする(男と女共に0から始まるので男は+Nしておく)
//男Aと女Bが親密な関係の場合頂点Aと頂点Bを結ぶ(costは-1*親密度にしておく)
//閉路ができないように辺を小さいコストから選んで行く->最小全域木->クラスカル法
//答えは人数*10000 + 最小全域木のコスト

#define MAX_V 20000 //頂点の最大数
#define MAX_E 50000 //辺の最大数

/////////////////////union-find木/////////////////////
int par[MAX_V]; //親
int rnk[MAX_V]; //木の深さ

//配列の初期化
void init(int V){
    FOR(i, 0, V){
        par[i] = i;
        rnk[i] = 0;
    }
}

//根を探す
int find(int x){
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
}

//合併
void unite(int x, int y){
    int px = find(x);
    int py = find(y);
    //すでに一緒なら何もしない
    if(px == py) return;
    //深い方の木にくっつける
    if(rnk[px]>=rnk[py]){
        par[py] = px;
        if(rnk[px]==rnk[py]) rnk[py]++;
    }
    else par[px] = py;
    return;
}

//同じグループかどうか=根が同じかどうか
bool same(int x, int y){
    return find(x) == find(y);
}

/////////////////////////////kruskal////////////////////////////

struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}

edge es[MAX_E]; //辺の数分
int V, R;

//最小全域木を求めるアルゴリズム=クラスカル法
int kruskal(){
    //短い順にソート
    sort(es, es+R, comp);
    int ret = 0;
    FOR(i, 0, R){
        edge e = es[i];
        if(same(e.u, e.v)) continue;
        ret += e.cost;
        unite(e.v, e.u);
    }
    return ret;
}

////////////////////////main////////////////////////

int main(){
    int n; //テストケースの数
    cin >> n;
    int N, M;
    //改行があるからgetlineいる？
    string s;
    getline(cin, s);
    FOR(i, 0, n){
        scanf("%d %d %d", &N, &M, &R);
        V = N + M;
        //union-find木の初期化
        init(V);
        //親密関係入力->esに保存
        FOR(j, 0, R){
            scanf("%d %d %d", &es[j].u, &es[j].v, &es[j].cost); //cinだとLTE
            //性別を区別する女(0~N-1) 男(N~N+M-1)
            es[j].v += N;
            //親密度分だけ安くなる
            //-1をかけて小さい方がより多くお金が安くなる->小さくなるパスを選ぶ
            //->閉路ができてはいけない->最小全域木
            es[j].cost *= -1;
        }
        getline(cin, s);
        cout << (V * 10000 + kruskal()) << endl;
    }
}

クラスカル法ではUnion-Find木を用いることで閉路ができるかどうか判定できるので、最小全域木を求めるのが簡単にできる.
クラスカル法を知らなかったので勉強になった.
クラスカル法 - Wikipedia

競プロ日記

nenuon

難しさ（初心者目線）

問題概要

方針

コード

コメント