首页 > 代码库 > bzoj 1458 网络流

bzoj 1458 网络流

2024-07-03 17:36:33   226人阅读

　　我们可以知道每行最多可以有多少个格子不用建点，设为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][2];
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,0,sizeof dis);
    que[1]=source; dis[source]=1;
    int h(0),t(1);
    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]+1;
            que[++t]=other[p];
            if (other[p]==sink) return 1;
        }
    }
    return 0;
}
 
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]+1) continue;
        if ((!rest)||(!len[p])) continue;
        int tmp=dinic(other[p],min(rest,len[p]));
        if (!tmp) dis[other[p]]=0;
        len[p]-=tmp; len[p^1]+=tmp; rest-=tmp;
    }
    return flow-rest;
}
 
int main() {
    scanf("%d%d%d",&n,&m,&k); l=1;
    for (int i=1;i<=n;i++) scanf("%d",&need[i][0]),need[i][0]=m-need[i][0];
    for (int i=1;i<=m;i++) scanf("%d",&need[i][1]),need[i][1]=n-need[i][1];
    for (int i=1;i<=k;i++) {
        int x,y; scanf("%d%d",&x,&y);
        flag[x][y]=1;
        need[x][0]--; need[y][1]--;
    }
    for (int i=1;i<=n;i++) if (need[i][0]<0) {
        printf("JIONG!\n");
        return 0;
    }
    for (int i=1;i<=m;i++) if (need[i][1]<0) {
        printf("JIONG!\n");
        return 0;
    }
    source=n+m+2; sink=source+1;
    for (int i=1;i<=n;i++) connect(source,i,need[i][0]),connect(i,source,0);
    for (int i=1;i<=m;i++) connect(i+n,sink,need[i][1]),connect(sink,i+n,0);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) if (!flag[i][j])
            connect(i,j+n,1),connect(j+n,i,0);
    ans=n*m-k;
    while (bfs()) ans-=dinic(source,inf);//,printf("%d\n",ans);
    printf("%d\n",ans);
    return 0;
}

 


联系
我们