链接
http://acm.hdu.edu.cn/showproblem.php?pid=1281
题意
对一个 $N*M$ 的棋盘，在格子里放尽量多国际象棋里的“车”，并且使得他们不能互相攻击，但是限制了只有某些格子才可以放。
某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。
求有多少个这样的重要点？
思路
先对行列求二分图最大匹配。
每次删除一条匹配边，重新匹配，若匹配数小于原先匹配数，说明删除边对应的点是重要点。
代码
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 <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=205;
int n,m,k,match[N],oldmatch[N];
bool st[N],vis[N][N];
VI g[N];
bool dfs(int u) {
for(int v=1;v<=m;v++) {
if(!vis[u][v]||st[v]) continue;
st[v]=true;
if(match[v+n]==-1||dfs(match[v+n])) {
match[u]=v+n;
match[v+n]=u;
return true;
}
}
return false;
}
int hungary() {
for(int i=1;i<=n+m;i++) match[i]=-1;
int res=0;
for(int i=1;i<=n;i++) {
if(match[i]!=-1) continue;
for(int j=1;j<=n+m;j++) st[j]=false;
if(dfs(i)) res++;
}
return res;
}
int main() {
int cs=0;
while(~scanf("%d%d%d",&n,&m,&k)) {
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
vis[i][j]=false;
for(int i=1;i<=k;i++) {
int x,y;
scanf("%d%d",&x,&y);
vis[x][y]=true;
}
int mx=hungary(),res=0;
for(int i=1;i<=n+m;i++) oldmatch[i]=match[i];
for(int i=1;i<=n;i++) {
vis[i][oldmatch[i]-n]=false;
if(hungary()<mx) res++;
vis[i][oldmatch[i]-n]=true;
}
printf("Board %d have %d important blanks for %d chessmen.\n",++cs,res,mx);
}
return 0;
}
|