HDU3870-s-t平面图最小割转最短路

痛定思痛。 2022-07-11 17:56 156阅读 0赞

**具体可以参见：（参考于）**

**             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\*（对偶图）**

![Center][]

**----------------------------------------------------------------------------------------**

**分割线**

**算法求解：**

**普通方法：**

如果按照普通的方法就是从s-t跑一遍最大流，但是如果一般这类题的点和边都是比较大的，

所以最大流很容易超时

**分析原因：**

既然给你的是一张s-t平面图，而他又有这么多的性质，显然我们是没有用到他的性质，

既然这样我们就要考虑怎么利用他的性质

**正解算法：**

从s-t平面图当中让原点s与汇点t连一条边，然后在构造他的对偶图G\*，然后令s\*为原点，t\*为汇点

我们通过性质就可以得知从s\*到t\*的一条路径就是原图的一个割，因此s\*到t\*的最短路就是最小割

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

![Center 1][]

**-----------------------------------------------------------------------------------------**

**分割线**

**算法例子： 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): 560**

Problem Description

A 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.

Input

The 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).

Output

For each case,print a line with a number indicating the minimium cost to arrest all thieves.

Sample Input

1
    3
    10 5 5
    6 6 20
    4 7 9

Sample Output

18
    
    
       
        Hint The map is like this:

**题目思路：**

s-t平面图最小割的裸题，例子当中的对偶图就是：

![Center 2][]

平面中的六个点代表代表被分成的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以下，还望大神们指点指点（留言给我）

[Center]: /images/20220711/46b8ab13886b4d6f8e0cc7c1044fc092.png
[Center 1]: /images/20220711/304a919a4c694f53b68d918b115eebcd.png
[Center 2]: /images/20220711/d00a825785c647a987ddc8b30afcb47b.png