[BZOJ3597][SCOI2014][网络流][分数规划]方伯伯运椰子[好题]

时间:2022-12-16 14:32:25

BZOJ上没有题干,这里直接贴一份:


[Description]

四川的方伯伯为了致富,决定引进海南的椰子树。方伯伯的椰子园十分现代化,椰子园中有一套独特的交通系统。
现在用点来表示交通节点,边来表示道路。这样,方伯伯的椰子园就可以看作一个有 n + 2 个交通节点,m条边的有向无环图。n +1 号点为入口,n +2 号点为出口。每条道路都有 6 个参数,ui,vi,ai,bi,ci,di,分别表示,该道路从 ui 号点通向 vi 号点,将它的容量压缩一次要 ai 的花费,容量扩大一次要 bi 的花费,该条道路当前的运输容量上限为 ci,并且每单位运输量通过该道路要 di 的费用。
在这个交通网络中,只有一条道路与起点相连。因为弄坏了这条道路就会导致整个交通网络瘫痪,聪明的方伯伯决定绝不对这条道路进行调整,也就是说,现在除了这条道路之外,对其余道路都可以进行调整。


有两种调整方式:
1. 选择一条道路,将其进行一次压缩,这条道路的容量会下降 1 单位。
2. 选择一条道路,将其进行一次扩容,这条道路的容量会上升 1 单位。

一条道路可以被多次调整。


由于很久以前,方伯伯就请过一个工程师,对这个交通网络进行过一次大的优化调整。所以现在所有的道路都被完全的利用起来了,即每条道路的负荷都是满的(每条道路的流量等于其容量)。
但方伯伯一想到自己的海南椰子会大丰收,就十分担心巨大的运输量下,会导致过多的花费。因此,方伯伯决定至少进行一次调整,调整之后,必须要保持每条道路满负荷,且总交通量不会减少。
设调整后的总费用是 Y,调整之前的总费用是 X。现在方伯伯想知道,最优调整比率是多少,即假设他进行了 k 次调整,(X - Y)/k最大能是多少?


注:总费用 = 交通网络的运输花费 + 调整的花费


[Input]

第 1 行包含 2 个整数 n,m
接下来 m 行代表 m 条边,表示这个交通网络。
每行 6 个整数,表示 ui,vi,ai,bi,ci,di.
接下来 1 行包含 1 条边,表示连接起点的边


[Output]

一个浮点数,保留 2 位小数,表示要求的答案,数据保证答案大于 0


[Sample]

样例输入  样例输出
6 7
1 2 0 0 1 1000
2 4 0 0 1 1000
4 6 0 0 1 1000
1 3 0 0 0 0
3 5 0 0 0 0
5 6 0 0 0 0
6 8 0 0 1 0
7 1 0 0 1 0
500.00

[Hint]

对于 20% 的数据, 1 <= n <= 5, 0 <= m <= 10.
对于 40% 的数据, 1 <= n <= 50, 0 <= m <= 300.
对于 100% 的数据,1 <= n <= 500,0 <= m <= 3000,1 <= ui, vi <= n + 2
0 <= ai, bi <= 50,0 <= ci <= 1000,0 <= di <= 1000


==============这里才是题解的开始==============

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

这道题由于保证有大于零的解,即费用一定能减少,所以增加流量是一定没有好下场的(费用一定增加)。那么我们只能通过调整流量来减少费用。这个时候我们需要——

消圈定理:残量网络里如果存在负费用圈,那么当前流不是最小费用流。因为通过增加残量网络负权边的流量,减少正权边的流量,一定能得到另一个更优的可行流。

由于这道题求的不是最优的费用流,而是最优的调整比率。所以最优解一定是只调整一个负权环(参见分数规划相关性质的证明自己YY去)。那么题目变成,求平均权值最小的负权环。

没什么说的了,最基本的分数规划题。

(本文是为了打破willinglive在这道题题解上的垄断而作。willinglive的题解地址:http://blog.csdn.net/willinglive/article/details/42772715

(话说昨年省选打酱油的时候还真是弱得1B啊,现在看来这么简单……)

不要随便看代码,不要随便看代码,不要随便看代码。因为很重要说以说三遍

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;

//Global Variables & Definitions
int N, M;
//End Global Variables & Definitions

//Map
int h[510];

struct edge {
int v, next;
double w;
} e[7000];

int ecnt;
void adde(int u, int v, double w) {
++ecnt;
e[ecnt].v = v;
e[ecnt].w = w;
e[ecnt].next = h[u];
h[u] = ecnt;
}

double dis[510];
int inq[510];
bool spfa(int n) {
inq[n] = 1;

int v;
for(int i = h[n];~i;i = e[i].next) if(dis[v = e[i].v] > dis[n] + e[i].w) {
dis[v] = dis[n] + e[i].w;

if(inq[v]) return true;
if(spfa(v)) return true;
}

inq[n] = 0;
return false;
}

bool TEST() {
for(int i = 0;i < 510;++i) { dis[i] = 0.0; inq[i] = 0; }

for(int i = 1;i <= N;++i) if(spfa(i)) return true;
return false;
}
//End Map

//Main Structure
inline void ir() {
memset(h, ecnt = -1, sizeof(h));
scanf("%d%d", &N, &M);
N += 2;

int u, v, a, b, c, d;
for(int i = 0;i < M;++i) {
scanf("%d%d%d%d%d%d", &u, &v, &a, &b, &c, &d);

adde(u, v, b + d);
if(c > 0) adde(v, u, a - d);
}
}

const double eps = 1e-3;
int main() {
ir();

double L = 0.0, R = 1e9;
while(R - L > eps) {
double mid = (L + R) / 2.;

for(int i = 0;i <= ecnt;++i) e[i].w += mid;

if(TEST())
L = mid;
else
R = mid;

for(int i = 0;i <= ecnt;++i) e[i].w -= mid;
}

printf("%.2f\n", (L + R) / 2.);
return 0;
}