BZOJ1001狼抓兔子(平面图最小割)

当前位置 : 首页 > 网页制作 > CSS > BZOJ1001狼抓兔子(平面图最小割)

BZOJ1001狼抓兔子(平面图最小割)

来源: 作者: 时间:2016-01-28 09:27
题目大意:给一个n*m的网格图,表示一个地图。起点(1,1),终点(n,m)。每条边上有一个权值,表示该路径上的兔流量。现在一些兔子从起点沿着边跑到终点。然后有一些大灰狼要抓这些兔
题目大意:给一个n*m的网格图,表示一个地图。起点(1,1),终点(n,m)。每条边上有一个权值,表示该路径上的兔流量。现在一些兔子从起点沿着边跑到终点。然后有一些大灰狼要抓这些兔子。一只狼能抓一只兔子。现在狼王想知道至少要派多少狼能堵住兔子的路。
 
题目分析:很裸的最小割问题。条件反射最大流搞之。但是这题的数据量是10M。n,m也比较大。硬上了一个最大流果然挂了。
 
这题的n,m范围是1000。这个网格图有n*m个点,有n*(m - 1) + m * (n - 1) + (n - 1) * (m - 1)条边。再加上网络流的复杂度O(n^2m),如果直接建图硬跑的话,复杂度最坏会达到O(n^3m^3),显然无法接受。
 
正确做法是先求给定网格图的对偶图,然后在对偶图上跑最大流,将最小割问题转化为最短路问题。好巧妙。具体可以戳这里。这篇论文讲的很详细。
 
具体做法是:
 
在给定的s-t平面图中,s到t连一条边,然后对这张图建对偶图。对偶图也比较好建:对于原图的每个面抽象出一个点,对于原图的每一条边,这条边相邻的2个面的点连边,边权为这条原图中边的权值。对原图的s-t加了 一条边,那么就相应的多了一个面,这个面抽象出新的点s',最外面的无界面抽象出点t',这样建好对偶图后我们会发现,对偶图中从s'到t'的任何一条路径都会将原图中的s和t分成2部分。即对偶图中s'到t'的任何一条路径都是原图的一个割,那么在对偶图中找的那条最短路便是原图的最小割!这个真是太巧妙了!!
 
再分析一下这种做法的复杂度:
 
首先对于改造后的原图:
 
点的数量:n*m
 
面的数量:2*(n - 1) * (m - 1) + 2
 
边的数量:n*(m - 1) + m * (n - 1) + (n - 1) * (m - 1) + 1
 
是满足欧拉定理的。
 
那么相应的对偶图:
 
点的数量:2*(n - 1) * (m - 1) + 2 = O(n*m)
 
面的数量:n*m
 
边的数量:n*(m - 1) + m * (n - 1) + (n - 1) * (m - 1) + 1 = 3*m*n - 2*(m+n) + 2
 
那么新图中跑最短路的话,如果用裸dijkstra,时间复杂度就降到了O(n^2m^2),还是比较大,不过已经优化很明显了。
 
spfa的话复杂度O(km*n),k为常数。
 
如果是dijkstra+heap的话,复杂度O(n*m*log(n*m)),已经很优秀了。
 
我是直接跑的spfa:)
 
好像很慢的样子,改天试试dijkstra+heap吧。。。
 
详情请见代码:
 
 
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
const int N = 1003;  
const int M = 2000005;  
const int inf = 0x3f3f3f3f;  
int head[M];  
struct node  
{  
    int to,next,val;  
}g[M + M];  
int m,n,nm,num;  
int dis[M],que[M];  
bool flag[M];  
void add(int s,int e,int v)  
{  
    g[num].to = e;  
    g[num].val = v;  
    g[num].next = head[s];  
    head[s] = num ++;  
}  
int nextint()  
{  
    int ret;  
    char c;  
    while((c = getchar()) > '9' || c < '0')  
        ;  
    ret = c - '0';  
    while((c = getchar()) >= '0' && c <= '9')  
        ret = ret * 10 + c - '0';  
    return ret;  
}  
void build()  
{  
    scanf("%d",&m);  
    nm = (n * m - m - n + 1)<<1;//there are nm nodes in new graph except s and t;  
    int i,j,tmp;  
    memset(head,-1,sizeof(head));  
    num = 0;  
  
    for(j = 1;j < m;j ++)//  
    {  
        scanf("%d",&tmp);  
        add(j,nm + 1,tmp);  
    }  
    for(i = 1;i < n - 1;i ++)  
    {  
        for(j = 1;j < m;j ++)  
        {  
            scanf("%d",&tmp);  
            add((i<<1)* (m - 1) + j,((i<<1) - 1) * (m - 1) + j,tmp);  
        }  
    }  
    for(j = 1;j < m;j ++)  
    {  
        scanf("%d",&tmp);  
        add(0,((n<<1)-3) * (m - 1) + j,tmp);  
    }  
  
    for(i = 0;i < n - 1;i ++)  
    {  
        for(j = 1;j <= m;j ++)  
        {  
            scanf("%d",&tmp);  
            if(j == 1)  
                add(0,(i<<1)*(m - 1) + m,tmp);  
            else if(j == m)  
                    add((i<<1|1)*(m - 1),nm + 1,tmp);  
                else  
                    add((i<<1)*(m  - 1) + j - 1,(i<<1)*(m - 1) + j + m - 1,tmp);  
        }  
    }  
  
    for(i = 0;i < n - 1;i ++)  
    {  
        for(j = 1;j < m;j ++)  
        {  
            scanf("%d",&tmp);  
            add((i<<1|1)*(m - 1) + j,(i<<1)*(m - 1) + j,tmp);  
        }  
    }  
}  
void SPFA()  
{  
    int i,front,rear;  
    memset(flag,false,sizeof(flag));  
    memset(dis,0x3f,sizeof(dis));  
    front = rear = dis[0] = 0;  
    que[rear ++] = 0;  
    flag[0] = true;  
    while(front != rear)  
    {  
        int u = que[front ++];  
        flag[u] = false;  
        if(front == M)  
            front = 0;  
        for(int i = head[u];~i;i = g[i].next)  
        {  
            int v = g[i].to;  
            if(dis[v] > dis[u] + g[i].val)  
            {  
                dis[v] = dis[u] + g[i].val;  
                if(flag[v] == false)  
                {  
                    flag[v] = true;  
                    que[rear ++] = v;  
                    if(rear == M)  
                        rear = 0;  
                }  
            }  
        }  
    }  
}  
void solve()  
{  
    SPFA();  
    printf("%d\n",dis[nm + 1]);  
}  
int main()  
{  
    while(scanf("%d",&n) != EOF)  
    {  
        build();  
        solve();  
    }  
    return 0;  
}  
//73072 kb  3688 ms  

 

 
Tag:

相关文章

网友评论

<