文理分科问题 网络流划分
题目大意
全班分科，每位同学分到文科能获得一定满意值，分到理科能获得一定满意值，如果上下左右的同学都被分到同一科也能增加一定的满意值，要求找到最优划分，使得满意值最大。
题解
对于这种把原集合一分为二的问题，容易想到它和最小割的形式类似，因为在最小割中所有点要么在s能到达的集合，要么在t联通的集合。
不考虑分组，我们可以把s连向所有节点，将边权设置成文科的满意值，同时将理科的满意值连向t。
加上分组问题就有点难办了，我们需要让一组人的收益增加当且仅当一组人选了一样的科目，这该怎么建图呢？
这就不得不说到一个建图时常用的技巧，无穷边：
一个显然的事实是，最小割一定不会包含无穷边，那么无穷边的作用就是强制两个点一荣俱荣，一损俱损保卫地球，有你有我，准确的说，如果无穷边的起点被包含在哪个点集，那么终点也在这个点集。（当然，本题中被割断后实际上起点不属于任何一个点集）
强制 s-u 之间在最小割中被割断或者 v-t 在最小割中被割断。
我们只需要对于每一组分配两个虚点，一个向s连一条表示选文，另一个向t连一条表示选理，再连向约束点表示条件就行了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int head[maxn],w[maxn],to[maxn],nxt[maxn],tot=1;
int s,t;
void add(int u,int v,int wi){
nxt[++tot]=head[u],to[head[u]=tot]=v,w[tot]=wi;
nxt[++tot]=head[v],to[head[v]=tot]=u,w[tot]=0;
}
int inf =0x3f3f3f3f;
int d[maxn];
int bfs(){
memset(d,0,sizeof(d));
queue<int>q;
q.push(s);
d[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(w[i]&&!d[v]){
d[v]=d[u]+1;
if(v==t)return 1;
q.push(v)
}
}
}
return 0;
}
int dinic(int u,int flow){
int rest=flow;
if(u==t)return flow;
for(int i=head[u];i&&rest;i=nxt[i]){
if(w[i]&&d[to[i]]==d[u]+1){
int x=dinic(to[i],min(rest,w[i]));
if(!x)d[to[i]]=0;
w[i]-=x;
w[i^1]+=x;
rest-=x;
}
}
return flow-rest;
}
int main(){
int n,m;
cin>>n>>m;
s=0,t=4*n*m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int x;
cin>>x;
add(s,(i-1)*m+j,x);
add((i-1)*m+j,(i-1)*m+j+n*m,inf);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int x;
cin>>x;
add((i-1)*m+j+n*m,t,x);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int x;
cin>>x;
add(s,(i-1)*m+j+2*n*m,x);
if(i>1)add((i-1)*m+j+2*n*m,(i-2)*n+j,inf);
if(j>1)add((i-1)*m+j+2*n*m,(i-1)*m+j-1,inf);
if(i<n)add((i-1)*m+j+2*n*m,(i)*n+j,inf);
if(j<m)add((i-1)*m+j+2*n*m,(i-1)*m+j+1,inf);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int x;
cin>>x;
add((i-1)*m+j+3*n*m,t,x);
if(i>1)add((i-1)*m+j+3*n*m,(i-2)*n+j+n*m,inf);
if(j>1)add((i-1)*m+j+3*n*m,(i-1)*m+j-1+n*m,inf);
if(i<n)add((i-1)*m+j+3*n*m,(i)*n+j+n*m,inf);
if(j<m)add((i-1)*m+j+3*n*m,(i-1)*m+j+1+n*m,inf);
}
int maxflow=0;
for(int i=2;i<=tot;i++){
if(w[i])cout<<to[i^1]<<" "<<to[i]<<" "<<w[i]<<endl;
}
while(bfs()){
while(int x=dinic(s,inf))maxflow+=x;
}
cout<<maxflow<<endl;
}