网络流之转换为对偶图

时间:2024-01-22 10:09:27

网络流之转换为对偶图

先来观察下面的这张图:

下面的这张却完全不行。

像这样任意两边的交点在顶点上的图我们称为平面图。

几条边围成一个区域,这个区域称为一个面。

对平面图,我们定义对偶图:

下图中黑色的是个平面图,红色的就是对偶图。其建立方法是,对每个面建一个点,只要有一条边是在两个面之间,我们就对这两个面对应的点连边(稍有些绕)。注意是有一条边就连线。

然后我们就得到萌萌哒的对偶图一张!

对偶图就有很多美妙的性质了。比如说,我们发现,对偶图的一条边就对应了一条割边。

既然如此的话,想想狼抓兔子,一条割边有一个容量,那么如果我们建它的对偶图,最短路就是最小割。

所以得出下面的重要定理:

对平面图来说,最大流 = 最小割 = 对偶图最短路

所以我们就可以稳一些跑出来狼抓兔子。

1001: [BeiJing2006]狼抓兔子

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 30078  Solved: 7908
[Submit][Status][Discuss]

Description

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

 

左上角点为(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只狼,
才能完全*这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的
狼的数量要最小。因为狼还要去找喜羊羊麻烦.

Input

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

Output

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

Sample Input

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

Sample Output

14

HINT

 

 2015.4.16新加数据一组,可能会卡掉从前可以过的程序。

 

Source

 
[Submit][Status][Discuss]


HOME Back

题目分析:

,每一个环中间都有一个点(类似于圆方树?) 然后每一条边会被相邻两个环中的点给穿插。最后我们要建立源点和汇点,让后让那些没有没有相邻环的连源汇点。

 

 这就是题目所给图的对偶图;

只要求源点到汇点的最短路径即可;

参考代码:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=2000006,INF=0x3fffffff,E=N*3;
  4 struct ARC {
  5     int u, val, next;
  6     inline void init(int a, int b, int c) {
  7         u=a, val=b, next=c;
  8     }
  9 } arc[E];
 10 int head[N], tot, S, T, n, m, dis[N];
 11 bool vs[N];
 12 
 13 struct data{
 14     int u, dis;
 15     data() {}
 16     data(int a, int b) : u(a), dis(b) {}
 17     bool operator < (const data &T) const {
 18         return dis>T.dis;
 19     }
 20 };
 21 
 22 inline void add_arc(int s, int t, int val) 
 23 {
 24     arc[tot].init(t, val, head[s]);
 25     head[s]=tot++;
 26 }
 27 
 28 priority_queue<data> Q;
 29 void Dijkstra() 
 30 {
 31     fill(dis, dis+T+1, INF);
 32     fill(vs, vs+T+1, 0);
 33     while(!Q.empty()) Q.pop();
 34     dis[S]=0, Q.push(data(S, 0));
 35     for(int u; !Q.empty(); ) 
 36     {
 37         u=Q.top().u, Q.pop();
 38         if(vs[u]) continue;
 39         if(u==T) 
 40         {
 41             printf("%d\n", dis[T]);
 42             break;
 43         }
 44         vs[u]=1;
 45         for(int e=head[u]; e!=-1; e=arc[e].next) {
 46             int v=arc[e].u;
 47             if(vs[v] || dis[u]+arc[e].val>=dis[v]) continue;
 48             dis[v]=dis[u]+arc[e].val;
 49             Q.push(data(v, dis[v]));
 50         }
 51     }
 52 }
 53 
 54 void read(int &x) {
 55     char c;
 56     while((c=getchar())<'0' || c>'9');
 57     x=c-'0';
 58     while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
 59 }
 60 
 61 void Input() {
 62     for(int i=0, id1, id2, a; i<=n-1; i++)
 63         for(int j=1; j<=m-1; j++) {
 64             read(a);
 65             id1=((i-1)*(m-1)+j)*2-1;
 66             id2=(i*(m-1)+j)*2;
 67             if(i==0) id1=T;
 68             else if(i==n-1) id2=S;
 69             add_arc(id1,id2,a);
 70             add_arc(id2,id1,a);
 71         }
 72 
 73     for(int i=1, id1, id2, a; i<=n-1; i++)
 74         for(int j=0; j<m; j++) {
 75             read(a);
 76             id1=((i-1)*(m-1)+j)*2;
 77             id2=((i-1)*(m-1)+j+1)*2-1;
 78             if(j==0) id1=S;
 79             else if(j==m-1) id2=T;
 80             add_arc(id1, id2, a);
 81             add_arc(id2, id1, a);
 82         }
 83 
 84     for(int i=1, id1, id2, a; i<=n-1; i++)
 85         for(int j=1; j<=m-1; j++) {
 86             read(a);
 87             id1=((i-1)*(m-1)+j)*2;
 88             id2=((i-1)*(m-1)+j)*2-1;
 89             add_arc(id1, id2, a);
 90             add_arc(id2, id1, a);
 91         }
 92 }
 93 
 94 int main() {
 95     read(n), read(m);
 96     S=0, T=(n-1)*(m-1)*2+1;
 97     fill(head, head+T+1, -1), tot=0;
 98     if(n==1 || m==1) 
 99     {
100         if(n>m) swap(n, m);
101         int ans=INF;
102         for(int i=1, a; i<m; i++) 
103         {
104             read(a);
105             if(ans>a) ans=a;
106         }
107         printf("%d\n", ans==INF?0:ans);
108     }
109     else Input(), Dijkstra();
110     return 0;
111 }
View Code