题面

题目链接

大秦 为你打开 题目传送门

备用题面

给定R行C列的格点，某些格点上有怪物,总共N个。可以在某行或者某列放置大炮，来消灭对应的行或列。

问最少要多少门大炮，才能把这些怪物完全消灭，以及安放的位置。

思路

如果把一个怪兽看作行号和列号相连的一条边，那么这时候答案其实就是这个二分图的最小点覆盖。然后就又是模板了

代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int R, C, n;
int mp[N][N];
int indr[N], indc[N];

int ma[N], tma[N];
int vis[N];
int visr[N], visc[N];

void Input() {
    scanf("%d%d%d", &R, &C, &n);
    int r, c;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &r, &c);
        mp[r][c] = 1;
        indr[r] = indc[c] = 1;
    }
}

int Dfs(int u) {
    for(int i = 1; i <= C; i++) {
        if(mp[u][i] && !vis[i]) {
            vis[i] = 1;
            if(!ma[i] || Dfs(ma[i])) {
                ma[i] = u;
                tma[u] = i;
                return 1;
            }
        }
    }
    return 0;
}

int Match() {
    int ret = 0;
    for(int i = 1; i <= R; i++) {
        memset(vis, 0, sizeof vis);
        if(Dfs(i)) ret++;
    }
    return ret;
}

int Get(int u) {
    visr[u] = 1;
    for(int i = 1; i <= C; i++) {
        if(mp[u][i] && !visc[i]) {
            visc[i] = 1;
            if(!ma[i] || Get(ma[i])) {
                return 1;
            }
        }
    }
    return 0;
}

void Work() {
    printf("%d ", Match());
    for(int i = 1; i <= R; i++) {
        if(!tma[i]) {
            Get(i);
        }
    }
    for(int i = 1; i <= R; i++) {
        if(!visr[i] && indr[i]) {
            printf("r%d ", i);
        }
    }
    for(int i = 1; i <= C; i++) {
        if(visc[i] && indc[i]) {
            printf("c%d ", i);
        }
    }
}

int main() {
    Input();
    Work();
    return 0;
}