题目描述

高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。

题解

这道题相当于给了我们一堆二元关系。容易想到用二元关系最小割来解决。

我们设学文的收益为w，学理的收益为l，同时学文的收益为w‘，同时学理的收益为w’。

那么考虑割集。

弄完之后发现有分数，乘个2就好了。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define N 30009

#define M 109

#define inf 1e9

using namespace std;

queue<int>q;

const int dx[4]={0,0,1,-1};

const int dy[4]={1,-1,0,0};

int num,tot=1,head[N],cur[N],deep[N],n,m,a[M][M],s_a[M][M],s[M][M],s_s[M][M],id[M][M];

long long ans;

inline int rd(){

	int x=0;char c=getchar();bool f=0;

	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	return f?-x:x;

}

struct edge{

    int n,to,l;

}e[N*30];

inline void add(int u,int v,int l,int tag){

    e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;

    e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=l*tag;

}

bool bfs(int s,int t){

    memcpy(cur,head,sizeof(head));

    memset(deep,0,sizeof(deep));

    q.push(s);deep[s]=1;

    while(!q.empty()){

        int u=q.front();q.pop();

        for(int i=head[u];i;i=e[i].n){

            int v=e[i].to;

            if(!deep[v]&&e[i].l){

                deep[v]=deep[u]+1;

                q.push(v);

            }

        }

    }

    return deep[t];

}

int dfs(int u,int t,int l){

    if(u==t||!l)return l;

    int flow=0,f;

    for(int &i=cur[u];i;i=e[i].n){

      int v=e[i].to;

      if(deep[v]==deep[u]+1&&(f=dfs(v,t,min(l,e[i].l)))){

      	  e[i].l-=f;e[i^1].l+=f;flow+=f;l-=f;

      	  if(!l)break;

      }

    }

    return flow;

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)

	  for(int j=1;j<=m;++j)a[i][j]=rd()*2,id[i][j]=++num,ans+=a[i][j];

	int S=0,T=num+1;

	for(int i=1;i<=n;++i)

	  for(int j=1;j<=m;++j)s[i][j]=rd()*2,ans+=s[i][j];

    for(int i=1;i<n;++i)

	  for(int j=1;j<=m;++j){

	    s_a[i][j]=rd();ans+=s_a[i][j]*2;

		a[i][j]+=s_a[i][j],a[i+1][j]+=s_a[i][j];

	  }

	for(int i=1;i<n;++i)

		for(int j=1;j<=m;++j){

			s_s[i][j]=rd();ans+=s_s[i][j]*2;

			s[i][j]+=s_s[i][j];s[i+1][j]+=s_s[i][j];

			add(id[i][j],id[i+1][j],s_a[i][j]+s_s[i][j],1);

		}

	for(int i=1;i<=n;++i)

	  for(int j=1;j<m;++j){

	    s_a[i][j]=rd();ans+=s_a[i][j]*2;

		a[i][j]+=s_a[i][j],a[i][j+1]+=s_a[i][j];

	   }

	for(int i=1;i<=n;++i)

	  for(int j=1;j<m;++j){

	    s_s[i][j]=rd();ans+=s_s[i][j]*2;

	    s[i][j]+=s_s[i][j];s[i][j+1]+=s_s[i][j];

	    add(id[i][j],id[i][j+1],s_a[i][j]+s_s[i][j],1);

	  }

	for(int i=1;i<=n;++i)

	   for(int j=1;j<=m;++j)add(S,id[i][j],a[i][j],0),add(id[i][j],T,s[i][j],0);

	while(bfs(S,T))ans-=dfs(S,T,inf);

	ans/=2;

	cout<<ans;

	return 0;

}