1458: 士兵占领
Time Limit: 10 Sec
Memory Limit: 64 MB
[
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
最少占领
，看起来像是让我们跑上下界，这等同于最多空出
就没有了
#include<iostream>
#include<cstring>
#include<cstdio>
#define INF 100000000
using namespace std;
const int N = 205;
int last[N*N],h[N*N],q[N*N],d[N*N],ans,cnt=1,T,S=0,n,m,K,l[N*N],ha[N*N],cur[N*N],a[N][N],tot;
struct Edge{
int to,next,v;
}e[210005];
void insert( int u, int v, int w ){
e[++cnt].to = v; e[cnt].next = last[u]; e[cnt].v = w; last[u] = cnt;
e[++cnt].to = u; e[cnt].next = last[v]; e[cnt].v = 0; last[v] = cnt;
}
bool bfs(){
memset(h,-1,sizeof(h));
int tail = 1, head = 0;
q[0] = S; h[0] = S;
while( tail != head ){
int now = q[head++];
for( int i = last[now]; i; i = e[i].next )
if( h[e[i].to] == -1 && e[i].v ){
h[e[i].to] = h[now] + 1;
q[tail++] = e[i].to;
}
}
return h[T] != -1;
}
int dfs( int x, int f ){
int w,used=0;
if( x == T ) return f;
for( int i = cur[x]; i; i = e[i].next )
if( h[e[i].to] == h[x] + 1 ){
w = dfs(e[i].to,min(e[i].v,f-used));
e[i].v -= w; e[i^1].v += w; used += w;
if( e[i].v ) cur[x] = i; if( f == used ) return f;
}
if( !used ) h[x] = -1;
return used;
}
void dinic(){
while( bfs() ){
for( int i = S; i <= T; i++ ) cur[i] = last[i];
ans += dfs(S,INF);
}
}
int main(){
scanf("%d%d%d", &m, &n, &K); tot = m*n-K; T = m+n+1;
for( int i = 1; i <= m; i++ ) scanf("%d", &l[i]), l[i] = n-l[i];
for( int i = 1; i <= n; i++ ) scanf("%d", &ha[i]), ha[i] = n-ha[i];
for( int i = 1,x,y; i <= K; i++ ){
scanf("%d%d", &x, &y);
a[x][y] = 1; l[x]--; ha[y]--;
if( l[x] < 0 ){ printf("JIONG!");return 0;}
if( ha[y] < 0 ){ printf("JIONG!");return 0;}
}
for( int i = 1; i <= m; i++ ) insert( S, i, l[i] );
for( int i = 1; i <= n; i++ ) insert( i+m, T, ha[i] );
for( int i = 1; i <= m; i++ )
for( int j = 1; j <= n; j++ )
if(!a[i][j])
insert( i, j+m, 1 );
dinic();
printf("%d", tot-ans);
return 0;
}
