Algoogle

Algorithm for Programming Contest

PKU 3041 Asteroids

Category: PKU Tag: bipartite-matching, max-flow

Asteroids

問題概要


N*Nのテーブル上にK個点がある.
縦, もしくは横に無限に長い線を引くとき, すべての点をカバーするには最小何本の線が必要か.

解法


2部グラフの最小点カバーなので最大マッチングを求めれば良い.
縦線を0~N-1, 横線をN~2*N-1と2つにわけて縦線と横線でマッチングする.

コード


(3041.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

vector<int> G[1024];
int N, K;
int match[1024], used[1024];

bool dfs(int v){
    used[v] = 1;
    for(int i = 0; i < G[v].size(); i++){
        int u = G[v][i], w = match[u];
        if(w < 0 or !used[w] and dfs(w)){
            match[v] = u;
            match[u] = v;
            return 1;
        }
    }
    return 0;
}
int b_match(){
    int res = 0;
    memset(match, -1, sizeof(match));
    for(int v = 0; v < 2*N; v++){
        if(match[v] < 0){
            memset(used, 0, sizeof(used));
            if(dfs(v)) res++;
        }
    }
    return res;
}

int main(){
    scanf("%d%d", &N, &K);
    for(int i = 0; i < K; i++){
        int r, c; scanf("%d%d", &r, &c);
        r--; c--;
        G[r].push_back(N+c);
        G[N+c].push_back(r);
    }
    printf("%d\n", b_match());
    return 0;
}

Comments