[BZOJ1475]方格取数 最小割


原题链接
方格取数问题是最小割典型题.将原图黑白染色后,源点向白点连边,容量为点权;黑点向汇点连边,容量为点权;白点向黑点连边,容量为inf.总点权-最小割即为答案.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1023
#define M 102333
using namespace std;
typedef long long ll;
const int inf=0x3bbbbbbb;
int n,s,t,ans,head[N],to[M],nxt[M],f[M],tot=1;
inline void add(int x,int y,int z)
{
    to[++tot]=y,nxt[tot]=head[x],head[x]=tot,f[tot]=z;
    to[++tot]=x,nxt[tot]=head[y],head[y]=tot,f[tot]=0;
}
int q[N],dis[N],l,r;
int bfs()
{
    l=1,r=0;
    memset(dis,-1,sizeof dis);
    q[++r]=s,dis[s]=0;
    int x,i,y;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=nxt[i])
        {
            y=to[i];
            if(dis[y]<0&&f[i]>0)
            {
                dis[y]=dis[x]+1;
                if(y==t)return 1;
                q[++r]=y;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)return flow;
    int a,tmp=flow;
    for(int i=head[x];i;i=nxt[i])if(dis[to[i]]==dis[x]+1&&f[i]>0)
    {
        a=dinic(to[i],min(tmp,f[i]));
        if(!a)dis[to[i]]=-1;
        f[i]-=a,f[i^1]+=a,tmp-=a;
        if(!tmp)return flow;
    }
    return flow-tmp;
}
int maxflow()
{
    int re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
inline int p(int i,int j){return (i-1)*n+j;}
inline int check(int i,int j)
{
    return i&&j&&i<=n&&j<=n;
}
int map[40][40];
int main()
{
    cin>>n;
    t=n*n+1;
    for(int j,i=1;i<=n;++i)
        for(j=1;j<=n;++j)
        {
            scanf("%d",&map[i][j]);
            ans+=map[i][j];
        }
    for(int j,i=1;i<=n;++i)
    {
        for(j=1;j<=n;++j)
        {
            if((i+j)&1)
            {
                add(s,p(i,j),map[i][j]);
                if(check(i-1,j))add(p(i,j),p(i-1,j),inf);
                if(check(i+1,j))add(p(i,j),p(i+1,j),inf);
                if(check(i,j+1))add(p(i,j),p(i,j+1),inf);
                if(check(i,j-1))add(p(i,j),p(i,j-1),inf);   
            }
            else add(p(i,j),t,map[i][j]);
        }
    }
    cout<<ans-maxflow();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注