Chrysanthemum's Blog

这道题目的模型就是裸的网络流，orz Gold_7，将源点与所有正的方块相连，将所有负的方块与汇点相连，然后将墙连接两个方块，注意要加双向边。

然后假设我们把所有房子都买了，要把两个正负不同的方块分开，要把其中一个不买或者买墙。所以最终答案就是所有房子的利益加起来减去最小割即可。

代码：

#include<cstdio>
#include<algorithm>
#define INF 1000000000
using namespace std;
int n,m,u,v,tot,source,sink,vs,cost,edgenum,ans;
int id[210][210],a[210][210],vet[4000010],next[4000010],head[4000010],maxv[4000010],gap[4000010],dis[4000010];
void add(int u,int v,int w)
{
    edgenum++;
    vet[edgenum]=v;
    next[edgenum]=head[u];
    head[u]=edgenum;
    maxv[edgenum]=w;
}
int dfs(int u,int aug)
{
    if (u==sink) return aug;
    int flow=0,mind=vs;
    for (int e=head[u];e;e=next[e])
    {
        int v=vet[e];
        if (maxv[e]<=0) continue;
        if (dis[u]==dis[v]+1)
        {
            int t=dfs(v,min(aug-flow,maxv[e]));
            maxv[e]-=t;
            if (e&1) maxv[e+1]+=t;else maxv[e-1]+=t;
            flow+=t;
            if (dis[source]>=vs) return flow;
            if (flow==aug) break;
        }
        mind=min(mind,dis[v]);
    }
    if (!flow)
    {
        gap[dis[u]]--;
        if (!gap[dis[u]]) dis[source]=vs;
        dis[u]=mind+1;
        gap[dis[u]]++;
    }
    return flow;
}
int maxflow(int s,int t)
{
    int ans=0;
    gap[0]=vs=t+1;
    source=s;sink=t;
    while (dis[source]<vs) ans+=dfs(source,INF);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            id[i][j]=++tot;
    tot++;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if (a[i][j]>0){ans+=a[i][j];add(0,id[i][j],a[i][j]);add(id[i][j],0,0);}else
            if (a[i][j]<0){ans-=a[i][j];add(id[i][j],tot,-a[i][j]);add(tot,id[i][j],0);}
        }
    for (int i=1;i<n;i++)
        for (int j=1;j<=m;j++)
        {
            scanf("%d",&cost);
            u=id[i][j];
            v=id[i+1][j];
            add(u,v,cost);
            add(v,u,cost);
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<m;j++)
        {
            scanf("%d",&cost);
            u=id[i][j];
            v=id[i][j+1];
            add(u,v,cost);
            add(v,u,cost);
        }
    printf("%d\n",ans-maxflow(0,tot));
}