#include<bits/stdc++.h>
#define calc(x,y) ((x-1)*m+y)
using namespace std;
typedef long long ll;
const int N=1e5+5,inf=1e9;
struct Edge{int to,r;ll c;};
vector<Edge>G[N];
int d[N],st,ed,n,m,tot,cnt;
ll sum;
inline bool bfs(){
	memset(d,-1,sizeof d);
	queue<int>q;q.push(st);d[st]=0;
	while(q.size()){
		int u=q.front();q.pop();
		for(const Edge&e:G[u])
			if(e.c&&d[e.to]==-1){
				d[e.to]=d[u]+1;q.push(e.to);
				if(e.to==ed)return true;
			}
	}
	return false;
}
inline ll dfs(int u,ll mf){
	if(u==ed)return mf;
	ll t=0;
	for(Edge&e:G[u])
		if(e.c&&d[e.to]==d[u]+1){
			ll f=dfs(e.to,min(mf-t,e.c));
			e.c-=f;G[e.to][e.r].c+=f;t+=f;
			if(t==mf)break;
		}
	if(!t)d[u]=-1;
	return t;
}
inline ll dinic(){
	ll mf=0;
	while(bfs())mf+=dfs(st,1e18);
	return mf;
}
void add(int u,int v,ll c){
	G[u].push_back({v,(int)G[v].size(),c});
	G[v].push_back({u,(int)G[u].size()-1,0});
}
int main(){
	scanf("%d%d",&n,&m);
	tot=n*m;
	st=0;
	ed=tot+2*n*(m-1)+2*(n-1)*m+1;
	cnt=tot;
	sum=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			int x;
			scanf("%d",&x);sum+=x;
			add(st,calc(i,j),x);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			int x;
			scanf("%d",&x);sum+=x;
			add(calc(i,j),ed,x);
		}
	for(int i=1;i<=n-1;i++)
		for(int j=1;j<=m;j++){
			int x;
			scanf("%d",&x);sum+=x;
			add(st,++cnt,x);
			add(cnt,calc(i,j),inf);
			add(cnt,calc(i+1,j),inf);
		}
	for(int i=1;i<=n-1;i++)
		for(int j=1;j<=m;j++){
			int x;
			scanf("%d",&x);sum+=x;
			add(++cnt,ed,x);
			add(calc(i,j),cnt,inf);
			add(calc(i+1,j),cnt,inf);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m-1;j++){
			int x;
			scanf("%d",&x);sum+=x;
			add(st,++cnt,x);
			add(cnt,calc(i,j),inf);
			add(cnt,calc(i,j+1),inf);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m-1;j++){
			int x;
			scanf("%d",&x);sum+=x;
			add(++cnt,ed,x);
			add(calc(i,j),cnt,inf);
			add(calc(i,j+1),cnt,inf);
		}
	printf("%lld\n",sum-dinic());
	return 0;
}

$$\Large\texttt{My Blog}$$

Description

题目链接：Luogu 1646

高一一班的座位表是个 $n\times m$ 的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。

作为计算机竞赛教练的 scp 大老板，想知道如何分配可以使得全班的喜悦值总和最大。

数据范围：$1\le n,m\le 100$，喜悦值均为小于等于 $5000$ 的非负整数。

Solution

考虑用网络流求解，总量减去最小割即为答案。

对于每个点 $(i,j)$，从 $s$ 连一条容量为选择文科的边，到 $t$ 连一条容量位选择理科的边。

对于 $(i,j)$ 和 $(i+1,j)$ 两个点的组合情况。假设这两个点同时选文科有 $w$ 的喜悦值，我们新建一个节点 $x$，从 $s$ 向 $x$ 连一条容量为喜悦值 $w$ 的边，再从 $x$ 向 $(i,j)$ 和 $(i+1,j)$ 分别连一条容量为 $\texttt{INF}$ 的边。对于左右前后、文科理科同理！

考虑这样做法的正确性：每个点自然只能选择一个科目（文科或理科），当某个点选择了文科 $s$，那么它向理科 $t$ 的边都应该要被断开。考虑哪些边会被断开：首先是它直接连向 $t$ 的边，其次是它和别的点组合连向 $t$ 的边，这样一来，这些边在网络图的割中是有贡献的，意味着这些边的容量在答案中没有贡献，正确性证明完毕。

时间复杂度：$O((nm)^3)$（$\texttt{Dinic}$）

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define FOR(i,a,b) for(int i=a;i<=b;++i)

const int N=1e5+5,M=5e6+5;
const int inf=1<<30;
int n,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

int id(int x,int y) {
	return (x-1)*m+y;
}
void add(int u,int v,int w) {
	ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
	add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
	memset(dep,0,sizeof(dep));
	memcpy(cnr,lnk,sizeof(lnk));
	std::queue<int> q;
	q.push(s),dep[s]=1;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=lnk[u];i;i=nxt[i]) {
			int v=ter[i];
			if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
		}
	}
	return dep[t];
}
int dfs(int u,int t,int flow) {
	if(u==t) return flow;
	int ans=0;
	for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
		cnr[u]=i;
		int v=ter[i];
		if(val[i]&&dep[v]==dep[u]+1) {
			int x=dfs(v,t,std::min(val[i],flow-ans));
			if(x) val[i]-=x,val[i^1]+=x,ans+=x;
		}
	}
	if(ans<flow) dep[u]=-1;
	return ans;
}
int dinic(int s,int t) {
	int ans=0;
	while(bfs(s,t)) {
		int x;
		while((x=dfs(s,t,inf))) ans+=x;
	}
	return ans;
}
int main() {
	scanf("%d%d",&n,&m);
	int s=0,t=n*m+2*n*(m-1)+2*(n-1)*m+1,cnt=n*m;
	int ans=0;
	FOR(i,1,n) FOR(j,1,m) {
		int x;
		scanf("%d",&x),ans+=x;
		addedge(s,id(i,j),x);
	}
	FOR(i,1,n) FOR(j,1,m) {
		int x;
		scanf("%d",&x),ans+=x;
		addedge(id(i,j),t,x);
	}
	FOR(i,1,n-1) FOR(j,1,m) {
		int x;
		scanf("%d",&x),ans+=x;
		addedge(s,++cnt,x);
		addedge(cnt,id(i,j),inf);
		addedge(cnt,id(i+1,j),inf);
	}
	FOR(i,1,n-1) FOR(j,1,m) {
		int x;
		scanf("%d",&x),ans+=x;
		addedge(++cnt,t,x);
		addedge(id(i,j),cnt,inf);
		addedge(id(i+1,j),cnt,inf);
	}
	FOR(i,1,n) FOR(j,1,m-1) {
		int x;
		scanf("%d",&x),ans+=x;
		addedge(s,++cnt,x);
		addedge(cnt,id(i,j),inf);
		addedge(cnt,id(i,j+1),inf);
	}
	FOR(i,1,n) FOR(j,1,m-1) {
		int x;
		scanf("%d",&x),ans+=x;
		addedge(++cnt,t,x);
		addedge(id(i,j),cnt,inf);
		addedge(id(i,j+1),cnt,inf);
	}
	printf("%d\n",ans-dinic(s,t));
	return 0;
}