题面
题目链接
大秦 为你打开 题目传送门
备用题面
给定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; }
|