POJ1459-Power Network

来源:互联网 时间:1970-01-01

转载请注明出处:優YoU http://user.qzone.qq.com/289065406/blog/1299339754

 

提示:BFS找增广链 + 压入重标法

解题思路:

多源多汇最大流问题

 

题目给出很多都是废话,特别是符号s(u),d(u),Con还有那条公式都别管,混淆视听

难点在于构图

 

电站p(u)均为源点,用户c(u)均为汇点,中转站当普通点处理

 

第一个误区是例图, 结点 和 边 都有x/y(流量和容量),这个很容易使人产生矛盾(因为学习最大流问题是,只有 边 才有流量和容量。

     但是不难发现,题目所给的例图中有多个源点,多个汇点,多个普通点,只有源点和汇点才标有 x/y,普通点没有标x/y,而且所给出的所有边都有x/y。 这无疑在促使我们对图做一个变形: 建议一个超级源s,一个超级汇t,使s指向所有源点,并把源点的 容量y 分别作为这些边的 容量,使所有汇点指向t,并把汇点的容量y分别作为这些边的 容量,然后本来是源点和汇点的点,全部变为普通点。这样就把“多源多汇最大流”变形为“单源单汇最大流”问题。

第二个误区就是流量值。 学习最大流问题时,会发现边上的流量值是给定初始值的,但是这题的输入只有容量,没有流量,很多人马上感觉到无从入手。其实边上的流量初始值为多少都没有所谓,解最大流需要用到的只有容量。但是一般为了方便起见, 会把所有边的流量初始化为0。这样做有一个最大的好处,就是可以回避 反向弧 的存在,这个下面详细叙述。

 

本题中要注意的是:

1、  如果输入中,某一点上有环,就无视掉。环是否存在不影响最终结果。

2、  一般两点之间都是单边,一旦存在双边也没有问题,因为由定义知两个方向的容量一定相等(其实不相等也无妨,因为其中有一条为 反向弧,前面已经提到 反向弧 是可以直接回避、无视的,因此反向弧上的容量为多少就不重要了),而且在寻找增广路的标号过程中,搜索的是未标号的点,就是说(u,v)这条弧即使是双向的,但一旦从u到达v后,就不能回头了,因为两者都被标记了,即另外一条弧就不起任何作用了。

 

下面详细说说为什么能够回避反向弧。

首先需要明确,任意一个点j上记录的信息有:

1、  寻找增光路时,除超级源s外,增广路上任一点j都有一个唯一的前驱i(i被记录在j)

2、  min{从i到j的容流差,l(vi)}

3、  构图时,除超级汇t外,图上任一点j都会直接指向一些点(这些点作为后继点,同在记录在j)

 

从这个特点可以知道,从超级源开始寻找增广路时,万一遇到双向边,正向弧,反向弧自动被回避。万一遇到单向边,如果是非饱和正向弧,就会继续走下去;如果是反向弧,这条弧必然是 零弧(每条边初始化流量均为0),定义知如果增广路有反向弧,它必须要是非零弧,而且由于反向弧每次都不会经过,所以在改进增广路时反向弧上的流量也不会被改变,永远为0,也就与最终结果无关了

 

最后当无法寻找增广路时,最大流就是与超级源s直接关联的边上的 流量之和

 

 1 /*BFS+压入重标法*/
2
3
4 //Memory Time
5 //384K 860MS
6
7 #include<iostream>
8 using namespace std;
9
10 const int inf=10001;
11
12 int n; //总节点数
13 int np; //电站数
14 int nc; //用户数
15 int line; //线路数
16 int cap[102][102]; //弧(u,v)的容量
17 int flow[102][102]; //弧(u,v)的流量
18 bool vist[102]; //标记点v是否已标号
19 int s,t; //超级源,超级汇
20
21 class info //当前点v的标记信息
22 {
23 public:
24 int pre; //当前点v的前驱u
25 int lv; //l(v)
26 int nei[101]; //当前结点直接指向的邻居结点
27 int pn; //邻居结点的指针
28 }node[102];
29
30 int min(int a,int b)
31 {
32 return a<b?a:b;
33 }
34
35 void back(void)
36 {
37 int x=t;
38 while(x!=s)
39 {
40 flow[ node[x].pre ][x] += node[t].lv; //改进增广路
41 x=node[x].pre;
42
43 }
44 return;
45 }
46
47 bool bfs(void)
48 {
49 memset(vist,false,sizeof(vist));
50 node[s].pre=-1;
51 node[s].lv=inf;
52 vist[s]=true;
53
54 int queue[102];
55 int head=0;
56 int tail=0;
57 queue[tail++]=s;
58
59 while(head<=tail-1) //注意,这是再也找不到增广路的结束条件
60 {
61 int x=queue[head];
62 int y;
63 for(int i=0;i<node[x].pn;i++)
64 {
65 y=node[x].nei[i];
66 if(!vist[y] && flow[x][y]<cap[x][y]) //搜索的目标要求是 未标记 & 非饱和弧
67 {
68 queue[tail++]=y;
69
70 vist[y]=true;
71 node[y].pre=x;
72 node[y].lv=min( node[x].lv , cap[x][y]-flow[x][y] );
73 }
74 if(vist[t]) //当超级汇被标记
75 break;
76 }
77 if(!vist[t])
78 head++;
79 else
80 return true; //搜索到一条增广路
81 }
82 return false;
83 }
84
85 int main(int i,int j,int u,int v,int z,char temp)
86 {
87 while(cin>>n>>np>>nc>>line)
88 {
89 /*Initial*/
90
91 s=n;
92 t=n+1;
93 for(i=0;i<n+1;i++)
94 node[i].pn=0;
95
96 /*Input & Structure Maps*/
97
98 for(i=1;i<=line;i++)
99 {
100 cin>>temp>>u>>temp>>v>>temp>>z;
101 if(u==v)
102 continue; //不需要环
103 cap[u][v]=z;
104 flow[u][v]=0; //每条边的流量都初始化为0
105 node[u].nei[ node[u].pn++ ]=v;
106 }
107 for(i=1;i<=np;i++)
108 {
109 cin>>temp>>v>>temp>>z;
110 cap[s][v]=z; //建立超级源,指向所有电站
111 flow[s][v]=0;
112 node[s].nei[ node[s].pn++ ]=v;
113 }
114 for(i=1;i<=nc;i++)
115 {
116 cin>>temp>>u>>temp>>z;
117 cap[u][t]=z; //建立超级汇,被所有用户指向
118 flow[u][t]=0;
119 node[u].nei[ node[u].pn++ ]=t;
120 }
121
122 /*标号法找增广轨*/
123
124 while(true)
125 {
126 if(bfs()) //如果能搜到到增广路
127 back(); //从超级汇开始回溯,改进增广路
128 else
129 {
130 int max=0; //输出最大流
131 for(i=0;i<node[s].pn;i++)
132 max+=flow[s][ node[s].nei[i] ];
133 cout<<max<<endl;
134 break;
135 }
136 }
137 }
138 return 0;
139 }

 

 

 

我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b我的新浪微博:http://weibo.com/lyy289065406我的腾讯微博:http://t.qq.com/liao5422我的QQ空间:http://user.qzone.qq.com/289065406我的百度空间:http://hi.baidu.com/you289065406/home我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


相关阅读:
Top