hdu 1281 棋盘游戏

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分图 最大匹配 唯一性

题意:给一个国际象棋棋盘,有些格子不能放车,有些格子能放,但是不能放车的格子并不是障碍,也就是说攻击不受这些格子影响。问最多能放几个车,另外有多少个格子是必须放车的,即这些格子不放车,车的总数就会减少

一开始想到的构图能求出最大匹配,但是求不出唯一性,把所有能放车的格子看做顶点标号,两个格子能攻击的话,就连一条无向边,最终问题转化为求解最大独立集,即集合里面的点都不互相攻击,但是这样做,无法搞出唯一性

正解的构图是,把行,列分别看做X,Y部,对于一个在(x,y)的棋子,就在X,Y部对应的点连一条边,这样二分图里面,边数就是能放棋子的格子数,然后求一次最大匹配即可,这样求出来的方案是不会互相攻击的,因为不能有行或者列被用2次,即不会出现同行同列的情况,自然就不会攻击到

至于唯一性,就是枚举删除一个格子,强制这个格子不能放棋子,看看最大匹配是否会减少,是的话,说明这个格子一定要放格子,就计数一次

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 110
#define M 10010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int row,col,m,tot,head[N],E;
int match[N],max_match;
bool vis[N];
struct edge{
int u,v,next;
}e[M];

inline void add(int u,int v){
e[tot].u = u; e[tot].v = v;
e[tot].next = head[u]; head[u] = tot++;
}

int dfs(int u){
for(int k = head[u]; k != -1; k = e[k].next){
if(k == E) continue;
int v = e[k].v;
if(!vis[v]){
vis[v] = true;
if(match[v] == -1 || dfs(match[v])){
match[v] = u; return 1;
}
}
}
return 0;
}

int MaxMatch(){
int ans = 0;
cl(match,-1);
for(int i = 1; i <= row; i++){
cl(vis,false);
ans += dfs(i);
}
return ans;
}

int main(){
int cas = 0;
while(scanf("%d%d%d",&row,&col,&m)!=EOF){
cl(head,-1); tot = 0;
for(int i = 0; i < m; i++){
int r,c;
scanf("%d%d",&r,&c);
add(r,c);
}
E = -1;
int max_match = MaxMatch();
int cnt = 0;
for(E = 0; E < tot; E++){ //枚举删除每条边,即每个点
int res = MaxMatch();
if(res != max_match) cnt++;
}
printf("Board %d have %d important blanks for %d chessmen.\n",++cas,cnt,max_match);
}
return 0;
}