题解 P4311 【士兵占领】

qwaszx · 2019-06-23 14:46:59 · 题解

补集转化，那么条件变成第i行不放士兵的位置不超过n-L[i]，第j列不放士兵的位置不超过m-C[i]，求最多不放多少个士兵.这个是个非常简单的网络流，连边(S,i,n-L[i]),(j+m,T,m-C[i]),(i,j+m,1)分别表示行限制、列限制、格子的选择

对于障碍物，钦定它不放，那么对应的限制减一并且不连这条边，最后再加回来就好了.

PS:数据非常的水...以至于你把n,m写反都有90分...

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e5,INF=2e9;
int q[N],cur[N],dis[N],n,m,k,mm,p[500][500],L[500],C[500],fst[N],nxt[N];
struct Edge{int v,w;}e[N];
void ade(int u,int v,int w)
{
    e[mm]=(Edge){v,w},nxt[mm]=fst[u],fst[u]=mm++;
}
void Link(int u,int v,int w){ade(u,v,w),ade(v,u,0);}
int dfs(int S,int lim)
{
    if(S==n+m+1||!lim)return lim;
    int add=0;
    for(int &i=cur[S];i!=-1&&lim;i=nxt[i])
    {
        int v=e[i].v,f;
        if(dis[v]!=dis[S]+1||!e[i].w||!(f=dfs(v,min(lim,e[i].w))))continue;
        e[i].w-=f,e[i^1].w+=f,add+=f,lim-=f;
    }
    return add;
}
int bfs(int S,int T)
{
    for(int i=S;i<=T;i++)dis[i]=0;
    int head=0,tail=1;q[1]=S,dis[S]=1;
    while(head<tail)
    {
        int u=q[++head];
        for(int i=fst[u];i!=-1;i=nxt[i])
        {
            int v=e[i].v;
            if(e[i].w&&!dis[v]){q[++tail]=v,dis[v]=dis[u]+1;}
        }
    }
    return dis[T];
}
int dinic()
{
    int ans=0;
    while(bfs(0,n+m+1))
    {
        for(int i=0;i<=n+m+1;i++)cur[i]=fst[i];
        ans+=dfs(0,INF);
    }
    return ans;
}
int main()
{
    scanf("%d%d%d",&m,&n,&k);for(int i=0;i<=n+m+1;i++)fst[i]=-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",&C[i]),C[i]=m-C[i];
    for(int i=1;i<=k;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);if(p[x][y])continue;
        L[x]--,C[y]--;p[x][y]=1;
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(!p[i][j])Link(i,j+m,1);
    for(int i=1;i<=m;i++)
    {
        if(L[i]<0){puts("JIONG");return 0;}
        Link(0,i,L[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(C[i]<0){puts("JIONG");return 0;}
        Link(i+m,n+m+1,C[i]);
    }
    cout<<n*m-(dinic()+k);
}