BZOJ3597【SCOI2014】方伯伯运椰子 <费用流>

Problem

【SCOI2014】方伯伯运椰子

$\mathrm{Time\;Limit:\;30\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description


Input

第一行包含二个整数$N$,$M$。
接下来$M$行代表$M$条边，表示这个交通网络。
每行六个整数，表示$U_i,V_i,A_i,B_i,C_i,D_i$。
接下来一行包含一条边，表示连接起点的边。

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\le N\le5000$，$0\le M\le3000$，$1\le U_i,V_i\le N+2$，$0\le A_i,B_i\le500$，$0\le C_i\le10000$，$0\le D_i\le1000$。

标签：费用流

Solution

妙不可言的费用流。

首先肯定需要二分答案，设当前答案是$tans$，那么第$i$条边压缩$1$流量花费$a_i-d_i+tans$，扩容$1$流量花费$b_i+d_i+tans$。

对于二分后的$check$，发现修改的同时维护流量守恒比较麻烦，不妨考虑先将所有流量都退掉，随后再逐一把不用退的流量增广回来，这样每次增广都可以保证流量守恒。那么初始费用为$\sum_{i=1}^{m}(a_i-d_i+tans)\times c_i$。

建模：
对于原图的第$i$条边：

• $u_i\to v_i$，流量$c_i$，费用$-(a_i-d_i+tans)$
• 若$u_i\ne S$，则$u_i\to v_i$，流量$\infty$，费用$(b_i+d_i+tans)$

这样跑最小费用最大流后判断$初始费用+最小增广费用<0$是否成立即可判断是否有$X-Y\ge0$。

正确性：
由于跑费用流，会优先增广费用小的边，而$(b_i+d_i+tans)-[-(a_i-d_i+tans)]=a_i+b_i+2\times tans\ge 0$，因此第一类边比第二类边小，一定会先走第一类边补到原先流量后再继续走第二类边扩容。

本文参考$qt66$的题解。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 100000
#define EPS 1e-5
#define INF 0x3f3f3f3f
#define mid ((l+r)/2)
using namespace std;
typedef double dnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct node {int v, c, nxt; dnt w;} E[MAX_M+5];
struct edge {int u, v, a, b, c, d;} e[MAX_M+5];
int n, m, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5];    dnt mic, tot;
void init() {s = n+1, t = n+2, cnt = 0, mic = tot = 0.0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, dnt w) {E[cnt] = (node){v, c, pr[u], w}, pr[u] = cnt++;}
void addedge(int u, int v, int c, dnt w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	memset(inq, false, sizeof inq);
    dnt d[MAX_N+5];	int cr[MAX_N+5];	for (int i = 1; i <= t; i++) d[i] = INF;
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;	dnt w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (fabs(d[t]-INF) <= EPS) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mic += 1.0*flow*d[t];	return true;
}
bool chk(dnt tans) {
    init();
    for (int i = 1; i <= m; i++)
        addedge(e[i].u, e[i].v, e[i].c, e[i].d-e[i].a-tans);
    for (int i = 1; i <= m; i++) if (e[i].u^s)
        addedge(e[i].u, e[i].v, INF, e[i].b+e[i].d+tans);
    for (int i = 1; i <= m; i++)
        tot += (e[i].a-e[i].d+tans)*e[i].c;
    while (SPFA()) ;	return tot+mic <= -EPS;
}
dnt bi_search(dnt l, dnt r) {
    dnt ret = -1.0;
    while (r-l >= EPS)
        if (!chk(mid)) r = mid;
        else ret = mid, l = mid;
    return ret;
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= m; i++)
        read(e[i].u), read(e[i].v), read(e[i].a), 
        read(e[i].b), read(e[i].c), read(e[i].d);
    return printf("%.2lf", bi_search(0.0, 30000.0)), 0;
}