NC20300. [SCOI2014]方伯伯运椰子
描述
现在用点来表示交通节点，边来表示道路。这样，方伯伯的椰子园就可以看作一个有 n + 2 个交通节点，m条边的有向无环图。n +1 号点为入口，n +2 号点为出口。每条道路都有 6 个参数，ui，vi，ai，bi，ci，di，分别表示，该道路从 ui 号点通向 vi 号点，将它的容量压缩一次要 ai 的花费，容量扩大一次要 bi 的花费，该条道路当前的运输容量上限为 ci，并且每单位运输量通过该道路要 di 的费用。
在这个交通网络中，只有一条道路与起点相连。因为弄坏了这条道路就会导致整个交通网络瘫痪，聪明的方伯伯决定绝不对这条道路进行调整，也就是说，现在除了这条道路之外，对其余道路都可以进行调整。
有两种调整方式：
选择一条道路，将其进行一次压缩，这条道路的容量会下降 1 单位。
选择一条道路，将其进行一次扩容，这条道路的容量会上升 1 单位。
一条道路可以被多次调整。
由于很久以前，方伯伯就请过一个工程师，对这个交通网络进行过一次大的优化调整。所以现在所有的道路都被完全的利用起来了，即每条道路的负荷都是满的（每条道路的流量等于其容量）。
但方伯伯一想到自己的海南椰子会大丰收，就十分担心巨大的运输量下，会导致过多的花费。因此，方伯伯决定至少进行一次调整，调整之后，必须要保持每条道路满负荷，且总交通量不会减少。
设调整后的总费用是 Y，调整之前的总费用是 X。现在方伯伯想知道，最优调整比率是多少，即假设他进行了 k 次调整，(X - Y)/k最大能是多少？
注：总费用 = 交通网络的运输花费 + 调整的花费
输入描述
第一行包含二个整数N，M接下来M行代表M条边，表示这个交通网络，每行六个整数，表示Ui,Vi,Ai,Bi,Ci,Di接下来一行包含一条边，表示连接起点的边
输出描述
一个浮点数，保留二位小数。表示答案，数据保证答案大于0
示例1
输入:
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
输出:
103.00
C++11(clang++ 3.9) 解法, 执行用时: 22ms, 内存消耗: 620K, 提交时间: 2019-03-09 19:00:36
#include<cstdio>
#include<cstring>
#define N 10005
using namespace std;
namespace runzhe2000
{
int n, m, last[N], ecnt, inq[N]; double dis[N];
struct pdge{int from, to, a, b, flow, cost;}pe[N];
struct edge{int next, to; double val;}e[N<<1];
void addedge(int a, int b, double c)
{
e[++ecnt] = (edge){last[a], b, c};
last[a] = ecnt;
}
bool dfs(int x)
{
inq[x] = 1;
for(int i = last[x]; i; i = e[i].next)
{
int y = e[i].to;
if(dis[x] + e[i].val < dis[y])
{
dis[y] = dis[x] + e[i].val;
if(inq[y] || dfs(y)) return 1;
}
}
inq[x] = 0; return 0;
}
bool check(double lim)
{
memset(last,0,sizeof(last)); ecnt=0;
for(int i = 1; i < m; i++)
{
addedge(pe[i].from,pe[i].to,pe[i].b+pe[i].cost+lim);
if(pe[i].flow)addedge(pe[i].to,pe[i].from,pe[i].a-pe[i].cost+lim);
}
for(int i = 1; i <= n; i++) dis[i] = 0, inq[i] = 0;
for(int i = 1; i <= n; i++) if(dfs(i)) return 1;
return 0;
}
void main()
{
scanf("%d%d",&n,&m); n += 2;
for(int i = 1; i <= m; i++)
scanf("%d%d%d%d%d%d",&pe[i].from,&pe[i].to,&pe[i].a,&pe[i].b,&pe[i].flow,&pe[i].cost);
double l = 0, r = 1e9;
for(; r - l > 1e-3; )
{
double mid = (l+r)/2;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2lf\n",(l+r)/2);
}
}
int main()
{
runzhe2000::main();
}