ST平面图最小割=ST平面图对偶图最短路
建图按边割开的边的边权建，特别地将S到T分成两个平面，设为SS和TT。
有一种情况是n=1或m=1，需要特殊处理。
注意到这种情况一定是一条链，边权为正，所以答案就是最远点了。
#include#include #include #include using namespace std;inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f;}const int MAXN=3000000;const int M=3000000;struct Edge{ int next,to,w;}e[M<<1];int ecnt,head[MAXN];inline void adds(int x,int y,int w){ e[++ecnt].next = head[x]; e[ecnt].to = y; e[ecnt].w = w; head[x] = ecnt;}inline void add(int x,int y,int w){ adds(x,y,w);adds(y,x,w);}struct Node{ int id,w; Node(int x=0,int y=0){id=x;w=y;} bool operator < (const Node &rhs) const { return w>rhs.w; }}top;priority_queue Q;int dis[MAXN],vis[MAXN];void dij(int s){ memset(dis,0x3f,sizeof(dis)); Q.push(Node(s,0));dis[s]=0; while(!Q.empty()){ top=Q.top();Q.pop(); int mnid=top.id,mn=top.w; if(vis[mnid]) continue; if(mn!=dis[mnid])continue;vis[mnid]=1; for(int i=head[mnid];i;i=e[i].next){ int v=e[i].to; if(dis[v]>dis[mnid]+e[i].w){ dis[v]=dis[mnid]+e[i].w; Q.push(Node(v,dis[v])); } } }}int n,m,S,T;#define id(x,y) ((((x)-1)*(m-1<<1))+(y))int main(){ n=rd();m=rd(); S=n*m*2+1;T=n*m*2+2; int x; for(int i=1;i<=n;i++){ for(int j=1;j<=m-1;j++){ x=rd(); if(i==1){add(id(1,j<<1),T,x);continue;} if(i==n){add(id(n-1,(j<<1)-1),S,x);continue;} add(id(i-1,(j<<1)-1),id(i,j<<1),x); } } for(int i=1;i<=n-1;i++){ for(int j=1;j<=m;j++){ x=rd(); if(j==1){add(id(i,(j<<1)-1),S,x);continue;} if(j==m){add(id(i,j-1<<1),T,x);continue;} add(id(i,(j-1)<<1),id(i,(j<<1)-1),x); } } for(int i=1;i<=n-1;i++){ for(int j=1;j<=m-1;j++){ x=rd(); add(id(i,(j<<1)-1),id(i,j<<1),x); } } dij(S); if(n!=1&&m!=1) return cout<