【BZOJ-1458】士兵占领最大流

1458: 士兵占领

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 782 Solved: 456
[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

Solution

仰慕黄学长....

把题目转化一下，使用最少的，转换成删去最多的，那么可用最大流求解

对于某行或某列，如果可以放的个数小于必须放的个数，那么直接JIONG!

那么对于源向各行连边，容量为可以放的格子数 – 需求的格子数

对于各列向汇连边，容量同上

从可放置的点的行连至列，容量为1

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define maxm 20000
#define maxn 500
int n,m,k;int L[110],C[110];
int zt[110][110];
int hang[110],lie[110],ans,tot,S,T;
struct Edgenode{int next,to,cap;}edge[maxm];
int head[maxn],cnt=1;
void add(int u,int v,int w)
{cnt++;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].cap=w;}
void insert(int u,int v,int w)
{add(u,v,w);add(v,u,0);}
//
int q[maxn],dis[maxn],cur[maxn];
bool bfs()
{
    for (int i=S; i<=T; i++) dis[i]=-1;
    int he=0,ta=1; q[0]=S; dis[S]=0;
    while (he<ta)
        {
            int now=q[he++];
            for (int i=head[now]; i; i=edge[i].next)
                if (edge[i].cap && dis[edge[i].to]==-1)
                    {
                        dis[edge[i].to]=dis[now]+1;
                        q[ta++]=edge[i].to;
                    }
        }
    return dis[T]!=-1;
}
int dfs(int loc,int low)
{
    if (loc==T) return low;
    int w,used=0;
    for (int i=cur[loc]; i; i=edge[i].next)
        if (edge[i].cap && dis[edge[i].to]==dis[loc]+1)
            {
                w=dfs(edge[i].to,min(low-used,edge[i].cap));
                edge[i].cap-=w; edge[i^1].cap+=w;
                used+=w; if (edge[i].cap) cur[loc]=i; 
                if (used==low) return low;
            }
    if (!used) dis[loc]=-1;
    return used;
}
#define inf 0x7fffffff
int dinic()
{
    int tmp=0;
    while (bfs())
        {
            for (int i=S; i<=T; i++) cur[i]=head[i];
            tmp+=dfs(S,inf);
        }
    return tmp;
}
void make()
{
    S=0,T=n+m+1;
    for (int i=1; i<=m; i++)
        insert(S,i,n-L[i]-hang[i]);
    for (int i=1; i<=n; i++)
        insert(i+m,T,m-C[i]-lie[T]);
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
            if (!zt[i][j]) insert(i,j+m,1);    
}
int main()
{
    m=read(),n=read(),k=read();
    for (int i=1; i<=m; i++) L[i]=read();
    for (int i=1; i<=n; i++) C[i]=read();
    tot=n*m-k;
    for (int x,y,i=1; i<=k; i++) 
        x=read(),y=read(),hang[x]++,lie[y]++,zt[x][y]=1;
    for (int i=1; i<=m; i++)
        if (hang[i]>n-L[i]) {puts("JIONG!");return 0;}
    for (int i=1; i<=n; i++)
        if (lie[i]>m-C[i]) {puts("JIONG!");return 0;}
    make();
    ans=dinic();
    printf("%d
",tot-ans);
    return 0;
}

好厉害...一开始没想到...看到这种网格图，就想黑白染色QAQ