先判无解
把整个棋盘都放上士兵, 只需求最多可以拿走多少个士兵即可.每一行看做一个点r(i), 每一列看做一个点c(i)
S->r(i), c(i)->T 连边, 容量为可以拿走的最大士兵数
(i,j)不是障碍格:r(i)->c(j),容量+oo
最后答案为n*m-k-maxflow
----------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
const int maxn = 209;
const int INF = 10000000;
struct edge {
int to, cap;
edge *next, *rev;
} E[maxn * maxn << 1], *pt = E, *head[maxn];
inline void add(int u, int v, int w) {
pt->to = v; pt->cap = w; pt->next = head[u]; head[u] = pt++;
}
inline void addedge(int u, int v, int w) {
add(u, v, w); add(v, u, 0);
head[u]->rev = head[v];
head[v]->rev = head[u];
}
edge *p[maxn], *cur[maxn];
int R[maxn], C[maxn], sumr[maxn], sumc[maxn], h[maxn], cnt[maxn], S, T, N;
bool ok[maxn][maxn];
int maxFlow() {
memset(cnt, 0, sizeof cnt);
memset(h, 0, sizeof h);
cnt[0] = N;
for(int i = 0; i < N; i++) cur[i] = head[i];
edge* e;
int flow = 0;
for(int x = S, A = INF; h[S] < N; ) {
for(e = cur[x]; e; e = e->next)
if(e->cap && h[e->to] + 1 == h[x]) break;
if(e) {
p[e->to] = cur[x] = e;
A = min(A, e->cap);
x = e->to;
if(x == T) {
flow += A;
for(; x != S; x = p[x]->rev->to) {
p[x]->cap -= A;
p[x]->rev->cap += A;
}
A = INF;
}
} else {
if(!--cnt[h[x]]) break;
h[x] = N;
for(e = head[x]; e; e = e->next) if(e->cap && h[e->to] + 1 < h[x]) {
h[x] = h[e->to] + 1;
cur[x] = e;
}
++cnt[h[x]];
if(x != S)
x = p[x]->rev->to;
}
}
return flow;
}
int main() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
S = 0; T = n + m + 1; N = T + 1;
memset(sumr, 0, sizeof sumr);
memset(sumc, 0, sizeof sumc);
memset(ok, -1, sizeof ok);
for(int i = 1; i <= n; i++) scanf("%d", R + i);
for(int i = 1; i <= m; i++) scanf("%d", C + i);
int tot = n * m - k;
while(k--) {
int x, y;
scanf("%d%d", &x, &y);
ok[x][y] = false;
sumr[x]++; sumc[y]++;
}
bool F = true;
for(int i = 1; i <= n; i++)
if(m - sumr[i] < R[i]) F = false;
for(int i = 1; i <= m; i++)
if(n - sumc[i] < C[i]) F = false;
if(F) {
for(int i = 1; i <= n; i++)
addedge(S, i, m - sumr[i] - R[i]);
for(int i = 1; i <= m; i++)
addedge(i + n, T, n - sumc[i] - C[i]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(ok[i][j]) addedge(i, j + n, INF);
printf("%d\n", tot - maxFlow());
} else
puts("JIONG!");
return 0;
}
----------------------------------------------------------------------
1458: 士兵占领
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 666 Solved: 386
[Submit][Status][Discuss]Description
有一个M * N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵, 第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。
Input
第一行两个数M, N, K分别表示棋盘的行数，列数以及障碍的个数。 第二行有M个数表示Li。 第三行有N个数表示Ci。 接下来有K行，每行两个数X, Y表示(X, Y)这个格子是障碍。
Output
输出一个数表示最少需要使用的士兵个数。如果无论放置多少个士兵都没有办法占领整个棋盘，输出”JIONG!” (不含引号)
Sample Input
4 4 4
1 1 1 1
0 1 0 3
1 4
2 2
3 3
4 3
Sample Output
4
数据范围
M, N <= 100, 0 <= K <= M * N
HINT
Source
BZOJ 1458: 士兵占领( 网络流 )
原文：http://www.cnblogs.com/JSZX11556/p/4851412.html
