HDU3870-s-t平面圖最小割轉最短路

2019-11-14 09:46:10

字體：大中小

來源：轉載

供稿：網友

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

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

Catch the Theves

Time Limit: 5000/2000 MS (java/Others) Memory Limit: 65768/32768 K (Java/Others)Total Submission(s): 1723 Accepted Submission(s): 560PRoblem DescriptionA group of thieves is approaching a museum in the country of zjsxzy,now they are in city A,and the museum is in city B,where keeps many broken legs of zjsxzy.Luckily,GW learned the conspiracy when he is watching stars and told it to zjsxzy.Zjsxzy decided to caught these thieves,and he let the police to do this,the police try to catch them on their way from A to B. Although the thieves might travel this way by more than one group, zjsxzy's Excellent police has already gather the statistics that the cost needed on each road to guard it. Now ,zjsxzy's conutry can be described as a N*N matrix A,Aij indicates the city(i,j) have bidirectionals road to city(i+1,j) and city(i,j+1),gurad anyone of them costs Aij.Now give you the map,help zjsxzy to calculate the minimium cost.We assume thieves may travel in any way,and we will catch all passing thieves on a road if we guard it. InputThe first line is an integer T,followed by T test cases.In each test case,the first line contains a number N(1<N<=400).The following N lines,each line is N numbers,the jth number of the ith line is Aij.The city A is always located on (1,1) and the city B is always located on (n,n).Of course,the city (i,j) at the last row or last line won't have road to (i,j+1) or (i+1,j). OutputFor each case,print a line with a number indicating the minimium cost to arrest all thieves. Sample Input

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以下，還望大神們指點指點（留言給我）