最小费用最大流，对数乘法换加法，浮点数比较

题意：

这道题看上去很裸，似乎就是一道最小费用流的题目。
需要注意的有三点：
1.这里面最小费用的计算是乘法，所以我们要对其取对数将其变为加法。
2.因为e(u,v)的cost为浮点数，所以再spfa算法中我们便不能再直接比较了。需要加上个eps否则会一直超时的。
3.我们注意到第一次走的时候不会产生费用，那么我们直接在该建边的两点间再建一条费用为零，容量为一的边就好了。

前两个雷我都踩了。。。。。。

代码如下：

#include<iostream>
#include<math.h>
#include<queue>
#include<iomanip>
using namespace std;
typedef pair<int, int> pii;
const double eps = 1e-9;
const double inf = 2e9;
const int max_n = 120;
const int max_m = 5500;
int n, m;
struct edge
{
    int to, cap, rev, next;
    double cost;
}E[max_m * 4];
int head[max_n];
int cnt = 1;

void add(int from, int to, int cap, double cost) {
    E[cnt].to = to;E[cnt].cap = cap;
    E[cnt].cost = cost;E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];head[from] = cnt++;

    E[cnt].to = from;E[cnt].cap = 0;
    E[cnt].cost = -cost;E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];head[to] = cnt++;
}

double dist[max_n];
bool used[max_n];
pii fa[max_n];
bool spfa(int s, int t) {
    fill(dist, dist + max_n, inf);
    fill(used, used + max_n, false);
    dist[s] = 0;used[s] = true;
    queue<int> que;que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        used[u] = false;
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (e.cap <= 0 || dist[e.to] <= dist[u] + e.cost)continue;
            dist[e.to] = dist[u] + e.cost;
            fa[e.to] = { u,i };
            if (used[e.to]) continue;
            que.push(e.to);
            used[e.to] = true;
        }
    }return dist[t] != inf;
}double matchpath(int s, int t, int& f) {
    int d = f;double res = 0;
    for (int cur = t;cur != s;cur = fa[cur].first) {
        edge& e = E[fa[cur].second];
        d = min(d, e.cap);
    }
    f -= d;res += d * dist[t];
    for (int cur = t;cur != s;cur = fa[cur].first) {
        edge& e = E[fa[cur].second];
        e.cap -= d;E[e.rev].cap += d;
    }
    return res;
}
double mcf(int s, int t, int f) {
    double res = 0;double cost = 0;
    while (f > 0 && spfa(s, t)) {
        cost = matchpath(s, t, f);
        res += cost;
    }return res;
}
int init() {
    fill(head, head + max_n, false);
    cnt = 1;int res = 0;
    int start = n + 1;int ed = start + 1;
    for (int i = 1;i <= n;i++) {
        int s, b;cin >> s >> b;res += s;
        if (s != 0) add(start, i, s, 0);
        if (b != 0) add(i, ed, b, 0);
    }for (int i = 1;i <= m;i++) {
        int u, v, c;double p;
        cin >> u >> v >> c >> p;
        if (c <= 0)continue;
        add(u, v, 1, 0);
        add(u, v, c - 1, -log2(1 - p));
    }return res;
}

int main() {
    ios::sync_with_stdio(0);
    int T;cin >> T;
    while (T-- && (cin >> n >> m))
        cout << fixed << setprecision(2) << 1.0 - pow(2, -mcf(n + 1, n + 2, init())) << endl;
}