bzoj刷题之旅上来就倒在了第一题上，乍一看是网络流，吓一跳，差点跑了。。
不过网上一查发现不用网络流也可以做，其实就是最小割的问题，先转换成对偶图，再跑最短路，就是原图的最小割
我记得之前大奶牛好像提过这种题，这次就当练手了
转换对偶图真是要吐啊，不过还好想了个比较简单的转换法
之后有时间把网络流的写法写了（小声
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define ll long long
using namespace std;
const int N=2e6+10,M=1e5+3;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int head[N],Next[N*3],ver[N*3],edge[N*3];
int dis[N],v[N]={0};
int tot=0;
int n,m;
int mn;
void add(int x,int y,int v){
ver[++tot]=y;
edge[tot]=v;
Next[tot]=head[x];
head[x]=tot;
}
struct node{
int p;
int v;
friend bool operator < (node n,node m){
return n.v>m.v;
}
};
int id(int x,int y){
return y+(x-1)*(m-1);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
mn=(m-1)*(n-1);
if(min(n,m)==1){
int ans=1e8;
for(int i=1;i<=max(m,n)-1;i++){
int k;
cin>>k;
ans=min(ans,k);
}
cout<<ans<<endl;
return 0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m-1;j++)
{
int k;cin>>k;
int u,v;
if(i==1)u=0;
else u=id(i-1,j)+mn;
if(i==n)v=2*mn+1;
else v=id(i,j);
add(u,v,k);
add(v,u,k);
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m;j++)
{
int k;cin>>k;
int u,v;
if(j==1)u=2*mn+1;
else u=id(i,j-1);
if(j==m)v=0;
else v=id(i,j)+mn;
add(u,v,k);
add(v,u,k);
}
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m-1;j++)
{
int k;cin>>k;
int u,v;
u=id(i,j);
v=id(i,j)+mn;
add(u,v,k);
add(v,u,k);
}
memset(dis,0x3f,sizeof(dis));
priority_queue<node> Q;
node c;
c.p=0;c.v=0;
Q.push(c);
dis[0]=0;
while(!Q.empty())
{
c=Q.top();
Q.pop();
int x=c.p;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
int vv=edge[i];
if(dis[y]>dis[x]+vv)
{
dis[y]=dis[x]+vv;
if(v[y])continue;
node d;
d.p=y;d.v=dis[y];
Q.push(d);
v[y]=1;
}
}
}
cout<<dis[2*mn+1]<<endl;
}