P4311 士兵占领[最大流]

题目地址

有一个$M * N$的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了$L_i$个士兵, 第j列至少放置了$C_j$个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。

---

考虑到说棋盘问题，选的行和列之间是有关联的，彼此制约着数量，就应该可以从网络流入手（然而如果我不是奔网络流刷题来的说不定会瞎写一发dp）

最小化答案，应该对应的是最大流的反向转化（也就是化加为减，求减数最大值，如最小路径覆盖），要不然就是最小割。反正这题辣鸡我是想了一会最小割没想出来才去转化问题的。最少要摆多少个，可以看成把棋盘能摆满的都摆满，再去删去没必要的点。这样的话构建二分图，左点集表示每行，右点集是列。s点向左点集连边容量为$n-L_i-x$ x表示本行障碍数量。容量意思就是我这行最多可以删????那么多点，再删就不合要求啦。右点集同理。$(x,y)$无障碍就在左右点集间连边容量为1，这样一条s到t的通路就是删除一个点$(x,y)$，然后做最大流后用总空格数减最大流即答案。

 

哦对了记得特判啊。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>inline char MIN(T&A,T B){return A<B?A=B,1:0;}
template<typename T>inline char MAX(T&A,T B){return A>B?A=B,1:0;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
    x=0;char c;while(!isdigit(c=getchar()))if(isalpha(c))return x=(int)c;
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();return x;
}
const int N=200+7,M=10400+7,INF=0x3f3f3f3f;
int w[M<<1],v[M<<1],Next[M<<1],Head[N<<1],cur[N<<1],dis[N<<1],tot=1,s,t,n,m;
inline void Addedge(int x,int y,int z){
    v[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;
    v[++tot]=x,Next[tot]=Head[y],Head[y]=tot,w[tot]=0;
}
#define y v[j]
inline char bfs(){
    queue<int> q;q.push(s),memset(dis,0,sizeof dis),dis[s]=1;
    for(register int i=1;i<=m+n+2;++i)cur[i]=Head[i];
    while(!q.empty()){
        int x=q.front();q.pop();
        for(register int j=Head[x];j;j=Next[j])if(w[j]&&!dis[y]){
            dis[y]=dis[x]+1,q.push(y);
            if(y==t)return 1;
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(!flow||x==t)return flow;
    int rest=flow,k;
    for(register int j=cur[x];j&&rest;cur[x]=j,j=Next[j])if(w[j]&&dis[y]==dis[x]+1){
        if(!(k=dinic(y,_min(rest,w[j]))))dis[y]=0;
        rest-=k,w[j]-=k,w[j^1]+=k;
    }
    return flow-rest;
}
#undef y
int a[N][N];
int x,y,k,res,cnt;

int main(){//freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);
    read(n),read(m),read(k);s=n+m+1,t=s+1;
    for(register int i=1;i<=n;++i)read(a[i][0]),a[i][0]=m-a[i][0];
    for(register int i=1;i<=m;++i)read(a[0][i]),a[0][i]=n-a[0][i];
    for(register int i=1;i<=k;++i)read(x),read(y),--a[x][0],--a[0][y],a[x][y]=1;
    for(register int i=1;i<=_max(n,m);++i)if(a[i][0]<0||a[0][i]<0){printf("JIONG!\n");return 0;}
    for(register int i=1;i<=n;++i)Addedge(s,i,a[i][0]);
    for(register int i=n+1;i<=n+m;++i)Addedge(i,t,a[0][i-n]);
    for(register int i=1;i<=n;++i)for(register int j=1;j<=m;++j)if(!a[i][j])Addedge(i,j+n,1),++cnt;
    while(bfs())res+=dinic(s,INF);
    printf("%d\n",cnt-res);
    return 0;
}