具體可以參見：（參考于）

             08年OI論文周冬《兩極相通——淺析最大—最小定理在信息學競賽中的應用》

問題描述：  

                  求一個s-t平面圖當中的最小割

--------------------------------------------------------------------------------------------------------------------

分割線

算法描述：

               幾個概念：

                            1，平面圖：給你的圖當中沒有相交的邊

                              2，s-t平面圖：即遠點與匯點位于平面圖的邊界

                              3，s-t平面圖最小割： 即從s-t的最大流，最大流即最小割

               幾個性質(zhì)：

                                  平面圖性質(zhì)：

                                       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*之間的關(guān)系：

                                         1，G的面數(shù)等于G*的點數(shù)，G*的點數(shù)等于G的面數(shù)，G與G*邊數(shù)相同 

                                          2，G*中的環(huán)對應G中的割一一對應 

                如圖：藍色線條的是G，紅色線條的是G*（對偶圖）

----------------------------------------------------------------------------------------

分割線

算法求解：

                   普通方法：

                                   如果按照普通的方法就是從s-t跑一遍最大流，但是如果一般這類題的點和邊都是比較大的，

                                   所以最大流很容易超時

                    分析原因：

                                    既然給你的是一張s-t平面圖，而他又有這么多的性質(zhì)，顯然我們是沒有用到他的性質(zhì)，

                                    既然這樣我們就要考慮怎么利用他的性質(zhì)

                   正解算法：

                                    從s-t平面圖當中讓原點s與匯點t連一條邊，然后在構(gòu)造他的對偶圖G*，然后令s*為原點，t*為匯點

                                   我們通過性質(zhì)就可以得知從s*到t*的一條路徑就是原圖的一個割，因此s*到t*的最短路就是最小割

            如圖：1*到8*的最短路就是1到8的最小割即最大流 

-----------------------------------------------------------------------------------------

分割線

算法例子： hdu3870

Catch the Theves

1310 5 56 6 204 7 9 Sample Output
18HintThe map is like this:   
    
題目思路：
                        s-t平面圖最小割的裸題，例子當中的對偶圖就是：
 
平面中的六個點代表代表被分成的6個平面，即對偶圖的六個點，而經(jīng)過原圖邊上的對偶圖的邊
表示該邊屬于的兩個平面即兩點有一條邊，從圖中我們很好看得出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以下，還望大神們指點指點（留言給我）