2021.12.02 P4001 [ICPC-Beijing 2006]狼抓兔子（最小割）
https://www.luogu.com.cn/problem/P4001
题意：
把图分成两部分需要的最小流量
分析：
……
我想，不用分析了吧，就差明晃晃地写着这是最小割了……
那我把这道妙题拎出来干啥？
无向边反向边初始化为和正向的边边权相同的边！
代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e6+10;
const int inf=(1<<30);
int n,m;
int cnt=1,head[N],dep[N],cur[N];
struct node{
int to,next,val;
}a[N*6];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline void addi(int u,int v,int w){
++cnt;
a[cnt].to=v;
a[cnt].val=w;
a[cnt].next=head[u];
head[u]=cnt;
}
inline void add(int u,int v,int w){
addi(u,v,w);addi(v,u,w);
}
inline int bfs(int s,int t){
memset(dep,0,sizeof(dep));
memcpy(cur,head,sizeof(head));
queue<int>q;
dep[s]=1;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(!dep[v]&&a[i].val)dep[v]=dep[x]+1,q.push(v);
}
}
return dep[t];
}
inline int dfs(int x,int t,int f){
if(x==t)return f;
int ans=0;
for(int i=cur[x];i&&f>ans;i=a[i].next){
cur[x]=i;
int v=a[i].to,fi=0;
if(a[i].val&&dep[v]==dep[x]+1&&(fi=dfs(v,t,min(f-ans,a[i].val)))>0)
a[i].val-=fi,a[i^1].val+=fi,ans+=fi;
}
return ans;
}
inline int Dinic(int s,int t){
int flow=0;
while(bfs(s,t)){
int x=0;
if((x=dfs(s,t,inf))>0)flow+=x;
}
return flow;
}
inline int id(int x,int y){
return (x-1)*m+y;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++)for(int j=1;j<m;j++){
int x=read();
add(id(i,j),id(i,j+1),x);
}
for(int i=1;i<n;i++)for(int j=1;j<=m;j++){
int x=read();
add(id(i,j),id(i+1,j),x);
}
for(int i=1;i<n;i++)for(int j=1;j<m;j++){
int x=read();
add(id(i,j),id(i+1,j+1),x);
}
cout<<Dinic(1,n*m);
return 0;
}
