[文章目录]
Description
高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
转化为最小割。额外代价和非集合中状态相连。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define M 301000
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t,sum;
int head[61000],to[M],nxt[M],f[M],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[61000];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m); int x; s=5*n*m+1; t=s+1;
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
{
scanf("%d",&x); sum+=x;
add(s,(i-1)*m+j,x);
}
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
{
scanf("%d",&x); sum+=x;
add((i-1)*m+j,t,x);
}
int tot=n*m;
for(int i=1;i<n;++i) for(int j=1;j<=m;++j)
{
scanf("%d",&x); sum+=x; ++tot;
add(s,tot,x); add(tot,(i-1)*m+j,inf); add(tot,i*m+j,inf);
}
for(int i=1;i<n;++i) for(int j=1;j<=m;++j)
{
scanf("%d",&x); sum+=x; ++tot;
add(tot,t,x); add((i-1)*m+j,tot,inf); add(i*m+j,tot,inf);
}
for(int i=1;i<=n;++i) for(int j=1;j<m;++j)
{
scanf("%d",&x); sum+=x; ++tot;
add(s,tot,x); add(tot,(i-1)*m+j,inf); add(tot,(i-1)*m+j+1,inf);
}
for(int i=1;i<=n;++i) for(int j=1;j<m;++j)
{
scanf("%d",&x); sum+=x; ++tot;
add(tot,t,x); add((i-1)*m+j,tot,inf); add((i-1)*m+j+1,tot,inf);
}
while(bfs()) sum-=dinic(s,inf);
printf("%d",sum);
return 0;
}