HDU 5988 Coding Contest（费用流）

题目地址
题意：ACM比赛有n个区域，每个区域有a[i]个人，b[i]个面包（每个人一个），然后如果没有面包，就要去别的区域拿，告诉你每个区域的连接的路，每条路第一个走这个路的人其他人都有p[i]的概率破坏网络，问你要所有的人都能吃到面包，问你破坏网络的概率最小为多少？
思路：破坏网络的概率最小就说保护网络的概率最大，然后对每个概率加上个log，然后概率之间的乘法就变成了加法了，然后我们就用MCMF就好了，建边的时候要拆成一个1和一个c[i]-1，因为第一个人不会破坏网络，所以要特殊处理。然后记得浮点数要用eps去判断相等的状态要不然会TLE。

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#define N 1010
#define M 100010
#define LL __int64
#define inf 2e9
#define lson l,mid,ans<<1
#define rson mid+1,r,ans<<1|1
#define getMid (l+r)>>1
#define movel ans<<1
#define mover ans<<1|1
using namespace std;
const LL mod = 1000000007;
const double eps = 1e-8;
int head[N];
int n, m, cnt;
struct node {
    int to;
    int cap;//剩余流量
    double money;//费用
    int next;
}edge[M];
struct MCMF {
    double len[N];//spfa求出的长度
    int pre[N];//spfa求出最短路径的前缀
    int path[N];//因为a->b可能有重复的边，所以记录是哪条边
    bool vis[N];
    void init() {
        memset(head, -1, sizeof(head));
        cnt = 0;
    }
    void add(int u, int v, int cap, double money) {//有向图
        edge[cnt].to = v, edge[cnt].cap = cap, edge[cnt].next = head[u], edge[cnt].money = money, head[u] = cnt++;
        edge[cnt].to = u, edge[cnt].cap = 0, edge[cnt].next = head[v], edge[cnt].money = -money, head[v] = cnt++;//反向边
    }
    bool spfa(int s, int t) {
        memset(vis, false, sizeof(vis));
        memset(pre, -1, sizeof(pre));
        memset(path, -1, sizeof(path));
        for (int i = 0; i < N; i++) {
            len[i] = inf;
        }
        queue<int> q;
        q.push(s);
        vis[s] = true;
        len[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = false;
            for (int i = head[u]; i != -1; i = edge[i].next) {
                int v = edge[i].to;
                if (len[v] - len[u] - edge[i].money > eps&&edge[i].cap > 0) {
                    len[v] = len[u] + edge[i].money;
                    pre[v] = u;
                    path[v] = i;
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
        }
        return len[t] != inf;
    }
    double MinCostMaxFlow(int s, int t) {
        double sum = 0;
        while (spfa(s, t)) {//找到最短路，从最短路径上找到最小流量
            int mmin = inf;
            for (int i = t; i != s && i != -1; i = pre[i]) {
                mmin = min(mmin, edge[path[i]].cap);//找到最小流量
            }
            for (int i = t; i != s && i != -1; i = pre[i]) {
                edge[path[i]].cap -= mmin;
                edge[path[i] ^ 1].cap += mmin;
                sum += mmin*edge[path[i]].money;
            }
        }
        return sum;
    }
};
int main() {
    MCMF mcmf;
    int T, n, m;
    int a, b, c;
    double d;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        mcmf.init();
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a, &b);
            int f = a - b;
            if (f > 0) {
                mcmf.add(0, i, f, 0);
            }
            else if(f < 0){
                mcmf.add(i, n + 1, -f, 0);
            }
        }
        while (m--) {
            scanf("%d%d%d%lf", &a, &b, &c, &d);
            d = -log2(1 - d);
            if (c > 0) {
                mcmf.add(a, b, 1, 0);
            }
            if (c - 1 > 0) {
                mcmf.add(a, b, c - 1, d);
            }
        }
        double cost = mcmf.MinCostMaxFlow(0, n + 1);
        cost = 1 - pow(2, -cost);
        printf("%.2lf\n", cost);
    }
    return 0;
}