题目描述
高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。
作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
输入格式
第一行两个正整数n，m。
接下来是六个矩阵
第一个矩阵为n行m列
此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。
第二个矩阵为n行m列
此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择理科获得的喜悦值。
第三个矩阵为n-1行m列
此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择文科获得的额外喜悦值。
第四个矩阵为n-1行m列
此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择理科获得的额外喜悦值。
第五个矩阵为n行m-1列
此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择文科获得的额外喜悦值。
第六个矩阵为n行m-1列
此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择理科获得的额外喜悦值。
输出格式
输出一个整数，表示喜悦值总和的最大值
输入
1 2
1 1
100 110
1
1000
输出
1210
说明/提示
【样例说明】
两人都选理，则获得100+110+1000的喜悦值。
对于100%以内的数据，n,m<=100 所有喜悦值均为小于等于5000的非负整数
解题：这道题与luogu P1361是用相同的做法。
这道题的做法是，对于每个同学，连一条边到理科，连一条边到文科，而对于其他的矩阵（一个同学和其他同学同时选理科或文科得到的值），新建一个点，然后连向相应的分科的点，最后我们选择割一条边，就相当于将那个点割到一个集合，我们要求剩下的值最大，也就是减去最少的边，使得源点和汇点不连通，所以求最小割即可。
代码：
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <bitset>
#include <queue>
#include <cstdio>
//#include <random>
#include <time.h>
using namespace std;
//std::mt19937 rnd(233);
#define pp pair<int,int>
#define ull unsigned long long
#define ls root<<1
#define rs root<<1|1
//#define int long long
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn =1e5+7;
const int Maxn = 5e6+7;
const double eps=1e-6;
const int mod=1e9+7;
struct edge{
int v,w,next;
}e[Maxn];
int head[maxn],cnt=1,cur[maxn],n,m,s,t,dis[maxn];
int tot;
void add(int a,int b,int c){
e[++cnt]=edge{b,c,head[a]};
head[a]=cnt;
//cout<<a<<' '<<b<<' '<<c<<endl;
}
bool bfs(){
for(int i=0;i<=tot+1;i++)dis[i]=0;
dis[s]=1;
queue<int> q;
q.push(s);
//cout<<s<<endl;
while(q.size()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(w>0 && !dis[v]){
dis[v]=dis[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int dfs(int u,int flow){
//if(u==t)cout<<"---";
//cout<<flow<<endl;
if(!flow || u==t)return flow;
int tflow=0;
for(int i=head[u];i;i=e[i].next){
cur[u]=e[i].next;
int v=e[i].v,w=e[i].w;
if(!w)continue;
if(dis[v]!=dis[u]+1)continue;
int tmp=dfs(v,min(flow,w));
e[i].w-=tmp;
e[i^1].w+=tmp;
flow-=tmp;
tflow+=tmp;
if(!flow)break;
}
if(!tflow)dis[u]=0;
return tflow;
}
signed main(){
scanf("%d%d",&n,&m);
s=0,t=n*m+2*n*(m-1)+2*(n-1)*m+1;
//cout<<t<<endl;
tot=n*m;
int res=0,x;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&x);
res+=x;
int a=(i-1)*m+j;
add(s,a,x);
add(a,s,0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&x);
res+=x;
int a=(i-1)*m+j;
add(a,t,x);
add(t,a,0);
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++){
++tot;
scanf("%d",&x);
res+=x;
int a=(i-1)*m+j;
add(s,tot,x);
add(tot,s,0);
add(tot,a,inf);
add(a,tot,0);
add(tot,a+m,inf);
add(a+m,tot,0);
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++){
++tot;
scanf("%d",&x);
res+=x;
int a=(i-1)*m+j;
add(tot,t,x);
add(t,tot,0);
add(a,tot,inf);
add(tot,a,0);
add(a+m,tot,inf);
add(tot,a+m,0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++){
++tot;
scanf("%d",&x);
res+=x;
int a=(i-1)*m+j;
add(s,tot,x);
add(tot,s,0);
add(tot,a,inf);
add(a,tot,0);
add(tot,a+1,inf);
add(a+1,tot,0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++){
++tot;
scanf("%d",&x);
res+=x;
int a=(i-1)*m+j;
add(tot,t,x);
add(t,tot,0);
add(a,tot,inf);
add(tot,a,0);
add(a+1,tot,inf);
add(tot,a+1,0);
}
int ans=0,flow;
while(bfs()){
//for(int i=0;i<=tot;i++)cur[i]=head[i];
while(flow=dfs(s,inf))ans+=flow;
//cout<<"--"<<endl;
}
//cout<<res<<' '<<ans<<endl;
cout<<res-ans<<endl;
}
小记：这道题建图方法和小M的作物那道题是一样的，但是写这道题的时候，还是出了一些问题，最开始找了挺久也没有找出来，最后重新写了一遍，但是 因为使用了cur数组，后面的样例都T了，所以有些时候cur数组对于优化是没有贡献的。
