具体可以参见：（参考于）
08年OI论文周冬《两极相通——浅析最大—最小定理在信息学竞赛中的应用》
问题描述：
求一个s-t平面图当中的最小割
--------------------------------------------------------------------------------------------------------------------
分割线
算法描述：
几个概念：
1，平面图：给你的图当中没有相交的边
2，s-t平面图：即远点与汇点位于平面图的边界
3，s-t平面图最小割： 即从s-t的最大流，最大流即最小割
几个性质：
平面图性质：
1. （欧拉公式）如果一个连通的平面图有n个点， m条边和f个面，那么f=m-n+2 2.
2， 每个平面图G都有一个与其对偶的平面图G*
2.1 G*中的每个点对应G中的一个面
2.2 对于G中的每条边e
2.2.1 e属于两个面f1、f2，加入边(f1*， f2*)
2.2.2 e只属于一个面f，加入回边(f*， f*)
平面图G与其对偶图G*之间的关系：
1，G的面数等于G*的点数，G*的点数等于G的面数，G与G*边数相同
2，G*中的环对应G中的割一一对应
如图：蓝色线条的是G，红色线条的是G*（对偶图）
----------------------------------------------------------------------------------------
分割线
算法求解：
普通方法：
如果按照普通的方法就是从s-t跑一遍最大流，但是如果一般这类题的点和边都是比较大的，
所以最大流很容易超时
分析原因：
既然给你的是一张s-t平面图，而他又有这么多的性质，显然我们是没有用到他的性质，
既然这样我们就要考虑怎么利用他的性质
正解算法：
从s-t平面图当中让原点s与汇点t连一条边，然后在构造他的对偶图G*，然后令s*为原点，t*为汇点
我们通过性质就可以得知从s*到t*的一条路径就是原图的一个割，因此s*到t*的最短路就是最小割
如图：1*到8*的最短路就是1到8的最小割即最大流
-----------------------------------------------------------------------------------------
分割线
算法例子： hdu3870
1310 5 56 6 204 7 9 Sample Output18HintThe map is like this:
题目思路：
s-t平面图最小割的裸题，例子当中的对偶图就是：
平面中的六个点代表代表被分成的6个平面，即对偶图的六个点，而经过原图边上的对偶图的边
表示该边属于的两个平面即两点有一条边，从图中我们很好看得出S*-T*的路径就是S-T的割
AC代码：
#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;const int maxn = 450*450;const int inf = 1e9;int hed[maxn],vis[maxn],dis[maxn];int n,e,nn;int s[505][505];struct st{ int v,w,nex;}edge[maxn<<2];void add(int u,int v,int w){ edge[e].v=v,edge[e].w = w,edge[e].nex=hed[u],hed[u]=e++;}void spfa(){ for(int i=1;i<=nn;i++)dis[i]=inf,vis[i]=0; dis[1]=0,vis[1]=1; queue<int>q;q.push(1); while(!q.empty()){ int u = q.front();q.pop();vis[u]=0; for(int i = hed[u];~i;i=edge[i].nex){ int v = edge[i].v; if(dis[v]>dis[u]+edge[i].w){ dis[v]=dis[u]+edge[i].w; if(!vis[v]){ vis[v]=1; q.push(v); } } } }}int main(){ int t;cin>>t; while(t--){ scanf("%d",&n); memset(hed,-1,sizeof(hed));e=1; nn=(n-1)*(n-1)+2; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&s[i][j]); if(i==1&&j!=n) //最上面的边 add(j+1,nn,s[i][j]),add(nn,j+1,s[i][j]); if(i==n&&j!=n) //最下面的边 add((i-2)*(n-1)+j+1,1,s[i][j]),add(1,(i-2)*(n-1)+j+1,s[i][j]); if(j==1&&i!=n) //最左面的边 add(1,(i-1)*(n-1)+2,s[i][j]),add((i-1)*(n-1)+2,1,s[i][j]); if(j==n&&i!=n) //最右面的边 add(nn,(i-1)*(n-1)+n,s[i][j]),add((i-1)*(n-1)+n,nn,s[i][j]); if(i!=1&&i!=n&&j!=n) //中间水平的边 add((i-2)*(n-1)+j+1,(i-1)*(n-1)+j+1,s[i][j]),add((i-1)*(n-1)+j+1,(i-2)*(n-1)+j+1,s[i][j]); if(j!=1&&j!=n&&i!=n) //中间垂直的边 add((i-1)*(n-1)+j+1,(i-1)*(n-1)+j,s[i][j]),add((i-1)*(n-1)+j,(i-1)*(n-1)+j+1,s[i][j]); } } spfa(); printf("%d/n",dis[nn]); } return 0;}PS：我这个代码跑了1500+ms 有的大神的算法只用了几百毫秒甚至100ms以下，还望大神们指点指点（留言给我）
新闻热点
疑难解答
