对偶图及其应用

发表于 | 分类于 | 阅读次数:

##模型
每个平面图 $G$ 都有一个与之对偶的平面图 $G^$
$G^$ 有如下性质：

  • $G^*$ 中的每个点对应 $G$ 中的一个面
  • 对于 $G$ 中的，每条边 $e$
    • $e$ 属于两个面 $f_1,f_2$ ，加入边 $(f_1^,f_2^)$
      • $e$ 只属于一个面 $f$ ，加入回边 $(f^,f^)$

对偶图

（图中加入了个绿色边围成的面，需要删除 $s^$ 与 $t^$ 之间的边）

这样我们通过求 $s^$ 到 $t^$ 的最短路，就可以求出原图中的最大流（最小割）

分析一下时间复杂度：

  • 直接用 Dinic 求最大流： $O(EV^2)$
  • 最大流转化最短路，用堆优化 Dijkstra ： $O(Vlog_2V)$

明显快了很多，然而实际跑起来差别并不大：测评结果

主要原因是 Dinic 加了优化之后时间复杂度很玄学……
##题目
###[bzoj1001]狼抓兔子[BeiJing2006]

Time Limit: 15 Sec Memory Limit: 162 MB

题目描述

现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到，但抓兔子还是比较在行的，
而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，
开始时所有的兔子都聚集在左上角(1,1)的窝里，现在它们要跑到右下解(N,M)的窝中去，狼王开始伏击
这些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为K，狼王需要安排同样数量的K只狼，
才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的
狼的数量要最小。因为狼还要去找喜羊羊麻烦.

输入格式

第一行为N,M.表示网格的大小，N,M均小于等于1000.
接下来分三部分
第一部分共N行，每行M-1个数，表示横向道路的权值.
第二部分共N-1行，每行M个数，表示纵向道路的权值.
第三部分共N-1行，每行M-1个数，表示斜向道路的权值.
输入文件保证不超过10M

输出格式

输出一个整数，表示参与伏击的狼的最小数量.

样例输入

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

样例输出

14

本题就是一到十分经典的用对偶图将最大流转化为最短路的题。

解题思路与之前讲的十分相似，只是建图比较麻烦，需要注意；还有一点就是当 $N=1$ 或 $M=1$ 时需要特判。

最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
 
const int MAXV=1e6+5,MAXE=3e6+5,INF=~0U>>1;//6
 
int N,M,S,T;
 
struct E{int next,to,cap;} e[MAXE<<2];
int ecnt=1,G[MAXV];
void addEdge(int u,int v,int c)
{
    e[++ecnt]=(E){G[u],v,c};G[u]=ecnt;
    e[++ecnt]=(E){G[v],u,0};G[v]=ecnt;
}
int dfn[MAXV];
queue<int> que;
bool calDfn()
{
    int i;
    memset(dfn,-1,sizeof(dfn));
    dfn[S]=0;que.push(S);
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(i=G[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dfn[v]==-1)
                dfn[v]=dfn[u]+1,que.push(v);
        }
    }
    return dfn[T]!=-1;
}
int iter[MAXV];
int calF(int u,int f)
{
    if(u==T) return f;
    for(int & i=iter[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].cap>0&&dfn[v]==dfn[u]+1)
        {
            int res=calF(v,min(f,e[i].cap));
            if(res>0)
            {
                e[i].cap-=res,e[i^1].cap+=res;
                return res;
            }
        }
    }
    return 0;
}
int dinic()
{
    int i,f,res=0;
    while(calDfn())
    {
        for(i=1;i<=N*M;i++) iter[i]=G[i];
        while((f=calF(S,INF))>0) res+=f;
    }
    return res;
}
int main()
{
    int i,j,u,v,c;
    scanf("%d%d",&N,&M);
    S=1,T=N*M;
    for(i=1;i<=N;i++)
        for(j=1;j<M;j++)
        {
            u=j+(i-1)*M,v=u+1;scanf("%d",&c);
            addEdge(u,v,c);addEdge(v,u,c);
        }
    for(i=1;i<N;i++)
        for(j=1;j<=M;j++)
        {
            u=j+(i-1)*M,v=u+M;scanf("%d",&c);
            addEdge(u,v,c);addEdge(v,u,c);
        }
    for(i=1;i<N;i++)
        for(j=1;j<M;j++)
        {
            u=j+(i-1)*M,v=u+M+1;scanf("%d",&c);
            addEdge(u,v,c);addEdge(v,u,c);
        }
    printf("%d\n",dinic());
    return 0;
}

最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

const int MAXV=2e6+105,MAXE=3e6+5,INF=~0U>>1;

int N,M,S,T;

struct E{int next,to,val;} e[MAXE<<1];int ecnt,G[MAXV];
void addEdge(int u,int v,int w)//双向边
{
	e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;
	e[++ecnt]=(E){G[v],u,w};G[v]=ecnt;
}

struct HN
{
	int id,v;
	bool operator<(const HN & ot)const
	{return v>ot.v;}
};

priority_queue<HN> heap;
bool inS[MAXV];int dis[MAXV];
int dijkstra()
{
	int i;
	for(i=1;i<=T;i++) dis[i]=INF;
	dis[S]=0;heap.push((HN){S,0});
	while(!heap.empty())
	{
		int u=heap.top().id;heap.pop();
		if(inS[u]) continue;
		inS[u]=true;
		for(i=G[u];i;i=e[i].next)
		{
			int v=e[i].to;
			if(inS[v]) continue;
			if(dis[v]>dis[u]+e[i].val)
			{
				dis[v]=dis[u]+e[i].val;
				heap.push((HN){v,dis[v]});
			}
		}
	}
	return dis[T];
}

int main()
{
	int i,j,w;
	scanf("%d%d",&N,&M);
	if(N==1||M==1)
	{
		if(N>M) swap(N,M);
		int ans=INF;
		for(i=1;i<=M;i++)
			scanf("%d",&w),ans=min(ans,w);
		printf("%d\n",ans);
	}else
	{
		S=2*(N-1)*(M-1)+1,T=S+1;
		//读取横向
		for(i=1;i<M;i++)
		{int v=i*2;scanf("%d",&w);addEdge(S,v,w);}
		for(i=2;i<N;i++)
			for(j=1;j<M;j++)
			{int u=2*((i-2)*(M-1)+j)-1,v=2*((i-1)*(M-1)+j);scanf("%d",&w);addEdge(u,v,w);}
		for(i=1;i<M;i++)
		{int u=2*((N-2)*(M-1)+i)-1;scanf("%d",&w);addEdge(u,T,w);}
		//读取纵向
		for(i=1;i<N;i++)
			for(j=1;j<=M;j++)
			{
				scanf("%d",&w);
				if(j==1)
				{int u=2*((i-1)*(M-1)+j)-1;addEdge(u,T,w);}
				else if(j==M)
				{int v=2*((i-1)*(M-1)+j-1);addEdge(S,v,w);}
				else
				{int u=2*((i-1)*(M-1)+j-1),v=u+1;addEdge(u,v,w);}
			}
		//读取斜向
		for(i=1;i<N;i++)
			for(j=1;j<M;j++)
			{int u=2*((i-1)*(M-1)+j)-1,v=u+1;scanf("%d",&w);addEdge(u,v,w);}
		printf("%d\n",dijkstra());
	}
	return 0;
}
/*
 *  ---------
 *	|1\2|3\4|
 *  |---|---|
 *  |5\6|7\8|
 *  |---|---|
 */