Coding Contest(概率费用流)

描述

传送门:HDU5988 - 2016ACM/ICPC亚洲区青岛站现场赛

A coding contest will be held in this university, in a huge playground. The whole playground would be divided into $N$ blocks, and there would be $M$ directed paths linking these blocks. The $i$-th path goes from the $u_i$-th block to the $v_i$-th block. Your task is to solve the lunch issue. According to the arrangement, there are $s_i$ competitors in the $i$-th block. Limited to the size of table, $b_i$ bags of lunch including breads, sausages and milk would be put in the $i$-th block. As a result, some competitors need to move to another block to access lunch. However, the playground is temporary, as a result there would be so many wires on the path.
For the $i$-th path, the wires have been stabilized at first and the first competitor who walker through it would not break the wires. Since then, however, when a person go through the $i$ - th path, there is a chance of $p_i$ to touch the wires and affect the whole networks. Moreover, to protect these wires, no more than $c_i$ competitors are allowed to walk through the $i$-th path.
Now you need to find a way for all competitors to get their lunch, and minimize the possibility of network crashing.

Input

The first line of input contains an integer $t$ which is the number of test cases. Then $t$ test cases follow.
For each test case, the first line consists of two integers $N$ $(N ≤ 100)$ and $M$ $(M ≤ 5000)$. Each of the next $N$ lines contains two integers $s_i$ and $b_i$ $(s_i , b_i ≤ 200)$.
Each of the next $M$ lines contains three integers $u_i$ , $v_i$ and $c_i$$(c_i ≤ 100)$ and a float-point number $p_i$$(0 < p_i < 1)$.
It is guaranteed that there is at least one way to let every competitor has lunch.

Output

For each turn of each case, output the minimum possibility that the networks would break down. Round it to $2$ digits.

Sample Input

1
2
3
4
5
6
7
8
9
10
1
4 4
2 0
0 3
3 0
0 3
1 2 5 0.5
3 2 5 0.5
1 4 5 0.5
3 4 5 0.5

Sample Output

1
0.50

思路

  • 看到这题开始就觉得是个网络流,而且应该是费用流。但是平时我们的费用流的费用都是单位流量的费用,而这题涉及到概率,有些不同。
  • 先说建图:
    • 判断每个点,如果这个点的人比食物多,就从源点到该点连一条边,否则从该点向汇点连一条边,容量为两者的差值,不发生危险的概率(费用)为$1$。
    • 由于每条边第一次走是不会发生危险的,所以需要特殊化处理,先建一条容量为$1$,费用为$1$的边,然后再建容量为$c-1$,费用为$1-p$的边。
    • 这样我们就要在这张图上最大化这个概率。(即求最大费用最大流)所以上述费用只要都取相反数,再跑最小费用最大流即可。
  • 在跑费用流的时候,由于原本的费用流中的费用是单位流量的费用,即$cost=\sum {p_i \times d_i}$,而在这题中,$cost=\prod {p_i ^ {d_i}}$。所以我们需要修改一下费用流中费用的计算。
    • 当然没有这么麻烦。我们可以两边取对数,即$\log cost = \sum {d_i \times \log p_i}$,这样就可以跑一个正常的费用流了,最后答案就是$1-e^{-cost}$。当然由于要计算的是最大费用,所以我们一样要取负对数!
  • 由于费用是double类型,所以在做最短路增广的时候要注意一下精度问题。

代码

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

struct Edge
{
int from, to, cap, flow;
double cost;
Edge(int u, int v, int c, int f, double w) : from(u), to(v), cap(c), flow(f), cost(w) {}
};

const int maxn = 105;
struct MCMF
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn]; //是否在队列中
double d[maxn]; //bellmanford
int p[maxn]; //上一条弧
int a[maxn]; //可改进量
void init(int n)
{
this->n = n;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap, double cost)
{
edges.pb(Edge(from, to, cap, 0, cost));
edges.pb(Edge(to, from, 0, 0, -cost));
m = edges.size();
G[from].pb(m - 2);
G[to].pb(m - 1);
}
bool BellmanFord(int s, int t, int& flow, double& cost)
{
for (int i = 0; i < n; i++) d[i] = INF;
clr(inq, 0);
d[s] = 0;
inq[s] = 1;
p[s] = 0;
a[s] = INF;
queue<int> q;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
inq[u] = 0;
for (int i = 0; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if (e.cap > e.flow && d[e.to] > d[u] + e.cost + eps)
{
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if (!inq[e.to])
{
q.push(e.to);
inq[e.to] = 1;
}
}
}
}
if (d[t] == INF) return false; // 当没有可增广的路时退出
flow += a[t];
cost += d[t] * a[t];
for (int u = t; u != s; u = edges[p[u]].from)
{
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
return true;
}
int MincostMaxflow(int s, int t, double& cost)
{
int flow = 0;
cost = 0;
while (BellmanFord(s, t, flow, cost))
;
return flow;
}
} ans;

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while (T--)
{
static int n, m;
scanf("%d%d", &n, &m);
int s = 0, t = n + 1;
ans.init(t + 1);
for (int i = 1; i <= n; i++)
{
static int a, b, c;
scanf("%d%d", &a, &b);
c = a - b;
if (c > 0)
ans.AddEdge(s, i, c, 0);
else if (c < 0)
ans.AddEdge(i, t, -c, 0);
}
while (m--)
{
static int u, v, c;
static double p;
scanf("%d%d%d%lf", &u, &v, &c, &p);
if (c == 0) continue;
if (c > 1) ans.AddEdge(u, v, c - 1, -log(1 - p));
ans.AddEdge(u, v, 1, 0);
}
double p;
ans.MincostMaxflow(s, t, p);
p = 1 - exp(-p);
printf("%.2f\n", p);
}
return 0;
}
捐助作者
0%