[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}$,而整个图不被破坏的概率就是

进行变量代换,令$1-p_i=e^{-w_i}$,即$w_i=\log\frac{1}{1-p_i}$,上式可以由积性函数转为和性函数:

最小化图被破坏的概率,那么就等价于最小化$\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)$。

那么,最终的答案为:

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;
}
}
用真金白银的方式为你想要的世界投票吧!