[hdu 5988. Coding Contest] zkw 最小费用最大流

发表于 | 分类于 | 阅读次数:

1. 题目链接

[hdu 5988. Coding Contest]

2. 题目描述

有 $N$ 个点，$M$ 条边的有向图 $(N\le 100, M\le 5000)$。任意一个点 $i$ 上有$s_i$ 个人，$b_i$ 份食物$(s_i, b_i\le 200)$。

任意一条边 $i$ 有几个属性 $u_i, v_i, c_i, p_i$ $(c_i\le 100, 0\lt p_i\lt 1)$。$u_i, v_i$ 分别表示有向边的两个顶点编号；$c_i$ 表示这条边的最大容量（最多允许几个人通过）；点$u_i$ 中的每个人可以沿着这条有向边移动到点 $v_i$，但是除了第一个经过这条边的人不会破坏这条边，剩下的人都会有 $p_i$ 的概率把这条边破坏。图中只要有一条边被破坏了，就认为图被破坏了。

现在需要保证所有人都能拿到一份食物的情况下，求出图被破坏的最小概率。

数据范围：

3. 解题思路

主要思路：拆边 + 对数函数将积性函数转为和性函数 + zkw 最小费用最大流。

首先，对于任意一个点来说，都优先把该点中的食物提供给这个点里面的人。然后可以把 $n$ 个节点分成两类节点，分别是满足 $s_i\gt b_i$ 、 $s_i\lt b_i$。第一类节点中的人移动到第二类节点中去获取食物。

对于边 $i$，设有 $f_i$ 个人经过这条边，那么，这条边不被破坏的概率是 $(1-p_i)^{f_i-1}$，而整个图不被破坏的概率就是
$$\prod_{f_i\gt 0}(1-p_i)^{f_i-1}$$

进行变量代换，令$1-p_i=e^{-w_i}$，即$w_i=\log\frac{1}{1-p_i}$，上式可以由积性函数转为和性函数：
$$\prod_{f_i\gt 0}e{-w_i(f_i-1)}=e{\sum_{f_i\gt 0}-w_i(f_i-1)}$$

最小化图被破坏的概率，那么就等价于最小化$\sum_{f_i\gt 0}w_i(f_i-1)$

然后，将所有的边 $i$ 拆成2条边来看，分别是一条流量为1，费用为0的有向边 和 一条流量为 $c_i-1$，费用为 $w_i$ 的有向边。

然后，很简单地就对最小费用最大流进行建模：

  • 首先，创建一个超级源点 $S$ 和一个超级汇点 $T$。
  • 然后从源点 $S$ 到所有第一类顶点 $u$ 中连一条流量为$s_u-b_u$，费用为0 的有向边；
  • 然后在所有的第二类节点 $v$ 到汇点 $T$ 连一条流量为 $b_v-s_v$，费用为 $0$ 的有向边。
  • 将原图中的所有边 $i$ 进行拆边，即:
    • $u_i$ 到 $v_i$ 中连一条流量为1，费用为0的有向边
    • 从 $u_i$ 到 $v_i$ 连一条流量为$c_i-1$，费用为$w_i=\log\frac{1}{1-p_i}$ 的有向边。

最后跑一下zkw 费用流，得到的费用流中的最小费用 $\mathrm{mincost}=\sum_{f_i\gt 0}w_i(f_i-1)$。

那么，最终的答案为：
$$\begin{align*}
\mathrm{result}&=1-\prod_{f_i\gt 0}e^{-w_i(f_i-1)}\
&=1-e^{\sum_{f_i\gt 0}-w_i(f_i-1)}\
&=1-e^{-\mathrm{mincost}}
\end{align*}$$

4. 参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;

const long double eps = 1e-8;
const int inf = 0x3f3f3f3f;

const int MAXN = 105;  // 点数
const int MAXM = 5005;
const int MAXE = 4 * MAXM; // 边数*2
template<class T> struct MinCostMaxFlow {
    struct Edge {
        int v, nxt;
        T cap, cost;
    } edge[MAXE];
    int head[MAXN], tot, src, des, n;
    bool vis[MAXN];
    T d[MAXN];
    T cost, mincost, maxflow;
    void init(int nx, int sx, int tx) {
        n = nx, src = sx, des = tx;
        tot = 0;
        mincost = maxflow = cost = 0;
        memset(head, -1, sizeof(head));
    }
    inline void add_edge(const int& u, const int& v, const T& cap, const T& cost) {
        edge[tot] = Edge{v, head[u], cap, cost};
        head[u] = tot ++;
        edge[tot] = Edge{u, head[v], 0, -cost};
        head[v] = tot ++;
    }
    T aug(int u, T f) {
        if(u == des) {
            mincost += cost * f;
            maxflow += f;
            return f;
        }
        vis[u] = true;
        T tmpf = f;

        for(int i = head[u]; ~i; i = edge[i].nxt) {
            if(edge[i].cap == 0 || edge[i].cost != 0 || vis[edge[i].v])
                continue;
            T delta = aug(edge[i].v, min(tmpf, edge[i].cap));
            edge[i].cap -= delta;
            edge[i ^ 1].cap += delta;
            tmpf -= delta;
            if(!tmpf) return f;
        }
        return f - tmpf;
    }
    bool modlabel() {
        for(int i = 0; i <= n; i++) d[i] = inf;
        d[des] = 0;
        deque<int> Q;
        Q.push_back(des);
        while(!Q.empty()) {
            int u = Q.front();
            Q.pop_front();
            T tmp;
            for(int i = head[u]; ~i; i = edge[i].nxt) {
                if(edge[i ^ 1].cap == 0 || (tmp = d[u] - edge[i].cost) >= d[edge[i].v]) continue;
                if((d[edge[i].v] = tmp) <= d[Q.empty() ? src : Q.front()]) Q.push_front(edge[i].v);
                else Q.push_back(edge[i].v);
            }
        }
        /** 根据需要，看节点编号从 0 开始还是从 1 开始 **/
        for(int u = 0; u <= n; u++) {
            for(int i = head[u]; i != -1; i = edge[i].nxt) {
                edge[i].cost += d[edge[i].v] - d[u];
            }
        }
        cost += d[src];
        return d[src] < inf;
    }
    void zkw() {
        while(modlabel()) {
            do {
                memset(vis, 0, sizeof(vis));
            } while(aug(src, inf));
        }
    }
};
MinCostMaxFlow<long double> mcmf;
int s[MAXM], b[MAXM];

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input.txt", "r", stdin);
#endif
    int T; scanf("%d", &T);
    while(T --) {
        int n, m; scanf("%d %d", &n, &m);
        int src = 0, dst = n + 1;
        mcmf.init(n + 2, src, dst);
        for(int i = 1; i <= n; ++i) {
            scanf("%d %d", &s[i], &b[i]);
            if(s[i] == b[i]) continue;
            if(s[i] > b[i]) {
                mcmf.add_edge(src, i, s[i] - b[i], 0);
            } else {
                mcmf.add_edge(i, dst, b[i] - s[i], 0);
            }
        }
        for(int i = 1; i <= m; ++i) {
            int u, v, c; double p;
            scanf("%d %d %d %lf", &u, &v, &c, &p);
            mcmf.add_edge(u, v, 1, 0);
            mcmf.add_edge(u, v, c - 1, log(1/(1-p)));
        }
        mcmf.zkw();
        cout << fixed << setprecision(2) << 1 - exp(-mcmf.mincost) << endl;
    }
}
坚持原创技术分享，您的支持将鼓励我继续创作！