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的边。这样我们就构造出了残量网络。

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

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

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double eps = 1e-3;
const int N = 1010;
struct edge {
    int to,next;
    double v;
}e[N * 10];
int st[N], tot, inq[N], n, m;
double dis[N];
void add(int x, int y, double z) {
    e[++tot].next = st[x], st[x] = tot;
    e[tot].to = y, e[tot].v = z;
}
bool spfa(int now) {
    inq[now] = 1;
    for (int i = st[now]; i; i = e[i].next)
        if (dis[e[i].to] > dis[now] + e[i].v) {
            dis[e[i].to] = dis[now] + e[i].v;
            if (inq[e[i].to]) return 1;
            if (spfa(e[i].to)) return 1;
        }
    inq[now] = 0;
    return 0;
}
bool check() {
    for (int i = 0; i < N; ++i)
        dis[i] = 0, inq[i] = 0;
    for (int i = 1; i <= n; ++i)
        if (spfa(i))
            return 1;
    return 0;
}
int u, v, a, b, c, d;
main() {
    scanf("%d%d", &n, &m), n += 2;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d%d%d%d", &u, &v, &a, &b, &c, &d);
        add(u, v, b + d);
        if (c > 0)
            add(v, u, a - d);
    }
    double l = 0, r = 1e9;
    while (r - l > eps) {
        double mid = (r + l) / 2.0;
        for (int i = 1; i <= tot; ++i)
            e[i].v += mid;
        if (check())
            l = mid;
        else
            r = mid;
        for (int i = 1; i <= tot; ++i)
            e[i].v -= mid;
    }
    printf("%.2lf\n", (l + r) / 2.0);
}