BZOJ-2132: 圈地计划（最小割）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2132

把所有收益累加起来，然后减去最小割即可。

sap秒杀了真开心~：

b8389b504fc2d5626a9b70f3e51190ef76c66c19.jpg.png

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
#define MAXN 110
#define MAXV 10010
#define inf 0x7fffffff
 
struct edge {
    edge *next,*pair;
    int t,f;
} *head[MAXV];
 
void Add(int s,int t,int f) {
    edge *p=new(edge);
    p->t=t,p->f=f,p->next=head[s];
    head[s]=p;
}
 
void AddEdge(int s,int t,int f) {
    Add(s,t,f),Add(t,s,0);
    head[s]->pair=head[t],head[t]->pair=head[s];
}
 
int node[MAXN][MAXN],V=0,S,T,color[MAXN][MAXN],sum=0,c[MAXN][MAXN];
int n,m;
 
void dfs(int x,int y,int col) {
    color[x][y]=col;
    if (x<n&&(!color[x+1][y]))dfs(x+1,y,col==1?2:1);
    if (y<m&&(!color[x][y+1]))dfs(x,y+1,col==1?2:1);
}
 
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
 
int h[MAXV],gap[MAXV];
edge *d[MAXV];
 
int sap(int v,int flow) {
    if (v==T) return flow;
    int rec=0;
    for (edge *p=d[v];p;p=p->next) if (p->f&&h[v]==h[p->t]+1) {
        int ret=sap(p->t,min(flow-rec,p->f));
        p->f-=ret,p->pair->f+=ret,d[v]=p;
        if ((rec+=ret)==flow) return flow;
    }
    if (!(--gap[h[v]])) h[S]=T;
    gap[++h[v]]++,d[v]=head[v];
    return rec;
}
 
int main() {
    scanf("%d%d",&n,&m);
    for (int i=0;i++<n;) for (int j=0;j++<m;) node[i][j]=++V;
    S=++V;
    T=++V;
    memset(color,0,sizeof(color));
    dfs(1,1,1);
    memset(head,0,sizeof(head));
    for (int i=0;i++<n;) for (int j=0;j++<m;) {
        int x;
        scanf("%d",&x);
        sum+=x;
        if (color[i][j]==1)AddEdge(S,node[i][j],x); else AddEdge(node[i][j],T,x);
    }
    for (int i=0;i++<n;) for (int j=0;j++<m;) {
        int x;
        scanf("%d",&x);
        sum+=x;
        if (color[i][j]==1)AddEdge(node[i][j],T,x); else AddEdge(S,node[i][j],x);
    }
    for (int i=0;i++<n;) for (int j=0;j++<m;)scanf("%d",&c[i][j]);
    for (int i=0;i++<n;) for (int j=0;j++<m;) {
        for (int k=0;k<4;k++) {
            int x=i+dir[k][0],y=j+dir[k][1];
            if (x&&x<=n&&y&&y<=m)AddEdge(node[i][j],node[x][y],c[i][j]+c[x][y]),sum+=c[i][j];
        }
    }
    int maxflow=0;
    memset(h,0,sizeof(h));
    memset(gap,0,sizeof(gap));
    for (int i=0;i++<T;) d[i]=head[i];
    gap[0]=T;
    while (h[S]<T) maxflow+=sap(S,inf);
    printf("%d\n",sum-maxflow); 
    return 0;
}