bzoj 1458 网络流

　　我们可以知道每行最多可以有多少个格子不用建点，设为x[i]，每列同理设为y[i]，那么我们连接(source,i,x[i]),(i,sink,y[i])表示我们将一个格子不建点，那么(i,j,flag[i][j])，当i,j这个格子可以建点的时候连边表示我们不在这个格子建点，那么n*m-k-最大流就是答案。　　

　　因为我们考虑可以在哪一个位置不放点，使得整个矩阵仍然合法，这样我们就可以知道最多有多少个合法的不建点的合法格子。　　

　　备注：开始想写有下限的最小可行流的着。

/**************************************************************

    Problem: 1458

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:28 ms

    Memory:1788 kb

****************************************************************/

//By BLADEVIL

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 400

#define maxm 30010

#define inf (~0U>>1)

using namespace std;

int n,m,k,source,sink,ans,l;

int need[maxn][];

int flag[maxn][maxn];

int que[maxn],dis[maxn],last[maxn],pre[maxm],other[maxm],len[maxm];

void connect(int x,int y,int z) {

    pre[++l]=last[x];

    last[x]=l;

    other[l]=y;

    len[l]=z;

    //if (z) printf("%d %d %d\n",x,y,z);

}

int bfs() {

    memset(dis,,sizeof dis);

    que[]=source; dis[source]=;

    int h(),t();

    while (h<t) {

        int cur(que[++h]);

        for (int p=last[cur];p;p=pre[p]) {

            if (dis[other[p]]) continue;

            if (!len[p]) continue;

            dis[other[p]]=dis[cur]+;

            que[++t]=other[p];

            if (other[p]==sink) return ;

        }

    }

    return ;

}

int dinic(int x,int flow) {

    if (x==sink) return flow;

    int rest=flow;

    for (int p=last[x];p;p=pre[p]) {

        if (!len[p]) continue;

        if (dis[other[p]]!=dis[x]+) continue;

        if ((!rest)||(!len[p])) continue;

        int tmp=dinic(other[p],min(rest,len[p]));

        if (!tmp) dis[other[p]]=;

        len[p]-=tmp; len[p^]+=tmp; rest-=tmp;

    }

    return flow-rest;

}

int main() {

    scanf("%d%d%d",&n,&m,&k); l=;

    for (int i=;i<=n;i++) scanf("%d",&need[i][]),need[i][]=m-need[i][];

    for (int i=;i<=m;i++) scanf("%d",&need[i][]),need[i][]=n-need[i][];

    for (int i=;i<=k;i++) {

        int x,y; scanf("%d%d",&x,&y);

        flag[x][y]=;

        need[x][]--; need[y][]--;

    }

    for (int i=;i<=n;i++) if (need[i][]<) {

        printf("JIONG!\n");

        return ;

    }

    for (int i=;i<=m;i++) if (need[i][]<) {

        printf("JIONG!\n");

        return ;

    }

    source=n+m+; sink=source+;

    for (int i=;i<=n;i++) connect(source,i,need[i][]),connect(i,source,);

    for (int i=;i<=m;i++) connect(i+n,sink,need[i][]),connect(sink,i+n,);

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++) if (!flag[i][j])

            connect(i,j+n,),connect(j+n,i,);

    ans=n*m-k;

    while (bfs()) ans-=dinic(source,inf);//,printf("%d\n",ans);

    printf("%d\n",ans);

    return ;

}

秒客网

bzoj 1458 网络流

相关文章