平面图最小割转对偶图最短路。
第一眼看到这题，显然是最小割嘛。。。根据最大流最小割定理，跑一遍最大流即可，但复杂度 O(n2∗m) ，显然要T啊。
然后我就学习了平面图最小割转对偶图最短路的想法，看完就会做了，资料传送门：两极相通——浅析最大最小定理在信息学竞赛中的应用
注意，对偶图最短路做法只使用于s-t平面图，不一定适用于一般图
这里顺便摘抄一些平面图的重要定义和性质，详细内容看资料：
·平面图：若图G可画在平面上，使得任意两条边都不会在非端点处相交，则称图G是平面图。
·s-t平面图：平面图中的一个点为源点s，另外一个点为汇点t，且s和t都在图中的无界面的边界上，这样的平面图称为s-t平面图
·欧拉公式：如果一个连通的平面图有n个点，m条边，f个域（面），那么f=m-n+2
·性质：每个平面图G都有一个与其对偶的平面图G*
话说这题用SPFA慢出翔了，推荐堆优化dijkstra（复杂度 O((n+m)∗log2n) ）
#include<cstdio> #include<queue> #include<cstring> #define add2(u,v,w) add(u,v,w);add(v,u,w) #define N 1005 using namespace std; int in() { int r=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')r=r*10+ch-'0',ch=getchar(); return r; } queue<int> q; bool vis[2200000]; int last[2200000], d[2200000], s=0, t=1, cnt=0; int pack(int x, int y, int side){return (x*1001+y)+side*1002005;} struct edge{int next,to,v;}e[2*3*N*N]; void add(int a, int b, int w) { e[++cnt]=(edge){last[a],b,w}; last[a]=cnt; } struct node { int id, v; node(){} node(int a, int b):id(a),v(b){} bool operator < (const node &a) const { return a.v<v; } }; int dijkstra() { priority_queue<node> q; memset(d,63,sizeof(d)); q.push(node(s,d[s]=0)); vis[s]=1; while(!q.empty()) { int x=q.top().id; q.pop(); vis[x]=1; if(x==t)break; for(int i = last[x]; i; i=e[i].next) { int y=e[i].to; if(!vis[y]&&d[x]+e[i].v<d[y]) { d[y]=d[x]+e[i].v; q.push(node(y,d[y])); } } } return d[t]; } int main() { int n, m, len; n=in();m=in(); if(n==1&&m==1)return !printf("0\n"); for(int i = 1; i <= n; i++) for(int j = 1; j < m; j++) { len=in(); add2(pack(i,j,1),pack(i-1,j,0),len); } for(int i = 1; i < n; i++) for(int j = 1; j <= m; j++) { len=in(); add2(pack(i,j,0),pack(i,j-1,1),len); } for(int i = 1; i < n; i++) for(int j = 1; j < m; j++) { len=in(); add2(pack(i,j,0),pack(i,j,1),len); } for(int j = 1; j <= m; j++) { add(pack(0,j,0),t,0); add(s,pack(n,j,1),0); } for(int i = 1; i <= n; i++) { add(pack(i,m,0),t,0); add(s,pack(i,0,1),0); } int ans=dijkstra(); printf("%d\n",ans); }