首页 > 题解 > bzoj 3597 [Scoi2014]方伯伯运椰子

bzoj 3597 [Scoi2014]方伯伯运椰子

Description

Input

第一行包含二个整数N,M

接下来M行代表M条边,表示这个交通网络
每行六个整数,表示Ui,Vi,Ai,Bi,Ci,Di
接下来一行包含一条边,表示连接起点的边
Output

一个浮点数,保留二位小数。表示答案,数据保证答案大于0

Sample Input

5 10

1 5 13 13 0 412

2 5 30 18 396 148

1 5 33 31 0 39

4 5 22 4 0 786

4 5 13 32 0 561

4 5 3 48 0 460

2 5 32 47 604 258

5 7 44 37 75 164

5 7 34 50 925 441

6 2 26 38 1000 22

Sample Output

103.00

HINT

1<=N<=5000

0<=M<=3000

1<=Ui,Vi<=N+2

0<=Ai,Bi<=500

0<=Ci<=10000

0<=Di<=1000

题解

考场遇到这种结论题真是要**了

消圈定理:费用流残量网络里面有负环就不是最小费用流。。

这题可以叫:方伯伯的费用流。对于原图中每一条边i,建一条正向的,容量正无穷,边权为bi + di的边;如果流量ci不为0,再建一条反向的,容量为ci,边权为ai – di的边。这样我们就构造出了残量网络。

由于这道题求的不是最优的费用流,而是最优的调整比率。所以最优解一定是只调整一个负权环。那么题目变成,求平均权值最小的负权环。

然后就是分数规划裸题了。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×