平面图我们离散课上讲过，在二维空间中可以写成不交叉边的图就是平面图，最小的非平面图有K5和K（3,3）
每个平面图都对应一个对偶图，对偶图中的最小环就是原图的最小割
如果删去对偶图中s-t这条边，就是相当于求最短路了
把原图中每个点在对偶图中标号，重新建图，在新图中跑最短路就行了
然后看一下平面图和对偶图之间的转化：
对偶图中的每一个点即为平面图中的某一个面，对偶图中任意两点间的线都是平面图中对应两平面公共边的割线，如果平面图中某一条边只属于一个面，那么在对偶图中就是一个环边
对偶图的边数等于平面图的边数，对偶图的点数等于平面图的面数
针对BZOJ1001
①把每一个图中的面积块当作新的点。
②每一条边都与两个面相连，把面看作点后，这条边连接这两个面化作的点，权值不变。
③连接起点与终点，把外面的最大平面分成两份，分别为最短路的起点与终点。
④跑一边最短路即可。
我感觉难在建图上，别的都非常好说
建图必须好好研究一下
1 #include<cstdio> 2 #include<cstring> 3 const int maxn=2000005; 4 int n,m,nm,cnt; 5 bool vi[maxn]; 6 int dis[maxn],g[maxn],q[maxn]; 7 struct Edge 8 { 9 int t,next,w; 10 }e[4*maxn]; 11 void insert(int u,int v,int w) 12 { 13 cnt++;e[cnt].t=v;e[cnt].w=w;e[cnt].next=g[u];g[u]=cnt; 14 cnt++;e[cnt].t=u;e[cnt].w=w;e[cnt].next=g[v];g[v]=cnt; 15 } 16 void spfa() 17 { 18 memset(dis,0x3f,sizeof(dis)); 19 dis[0]=0; 20 int h=0,t=1; 21 q[t]=0; 22 vi[0]=1; 23 while(h!=t) 24 { 25 h=h%maxn+1; 26 int u=q[h]; 27 vi[u]=0; 28 for(int tmp=g[u];tmp;tmp=e[tmp].next) 29 { 30 int v=e[tmp].t; 31 if(dis[v]>dis[u]+e[tmp].w) 32 { 33 dis[v]=dis[u]+e[tmp].w; 34 if(!vi[v]) 35 { 36 t=t%maxn+1; 37 vi[v]=1; 38 q[t]=v; 39 } 40 } 41 } 42 } 43 } 44 int main() 45 { 46 scanf("%d%d",&n,&m); 47 nm=(n*m-m-n+1)<<1; 48 int x; 49 for(int j=1;j<m;j++) 50 { 51 scanf("%d",&x); 52 insert(j,nm+1,x); 53 } 54 for(int i=1;i<n-1;i++) 55 { 56 for(int j=1;j<m;j++) 57 { 58 scanf("%d",&x); 59 insert((i<<1)*(m-1)+j,((i<<1)-1)*(m-1)+j,x); 60 } 61 } 62 for(int j=1;j<m;j++) 63 { 64 scanf("%d",&x); 65 insert(0,((n<<1)-3)*(m-1)+j,x); 66 } 67 for(int i=0;i<n-1;i++) 68 { 69 for(int j=1;j<=m;j++) 70 { 71 scanf("%d",&x); 72 if(j==1) insert(0,(i<<1)*(m-1)+m,x); 73 else if(j==m) insert((i<<1|1)*(m-1),nm+1,x); 74 else insert((i<<1)*(m-1)+j-1,(i<<1)*(m-1)+j+m-1,x); 75 } 76 } 77 for(int i=0;i<n-1;i++) 78 { 79 for(int j=1;j<m;j++) 80 { 81 scanf("%d",&x); 82 insert((i<<1|1)*(m-1)+j,(i<<1)*(m-1)+j,x); 83 } 84 } 85 spfa(); 86 printf("%d",dis[nm+1]); 87 return 0; 88 }