2016ACM/ICPC亚洲区青岛站 Coding Contest 费用流
题目描述
题目描述
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 ui-th block to the vi-th block. Your task is to solve the lunch issue. According to the arrangement, there are si competitors in the i-th block. Limited to the size of table, bi 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 pi to touch the wires and affect the whole networks. Moreover, to protect these wires, no more than ci 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.
输入描述:
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 si and bi (si,bi ≤ 200).
Each of the next M lines contains three integers ui,vi and ci(ci ≤ 100) and a float-point number pi(0 < pi < 1). It is guaranteed that there is at least one way to let every competitor has lunch.
输出描述:
For each turn of each case, output the minimum possibility that the networks would break down. Round it to 2 digits.
题意(博主的鬼畜翻译):
有n个点,m条边,每个点有(a_i)竞争者，和(b_i)的食物,每个人要吃饭，可以通过一些路径。每条路径电线有(p_i)的概率碰坏，第一个人一定不会坏。问怎么走每个人都能获得食物，切坏的概率最小。
分析:
首先这个输入u -> v 花费 (c_i) 概率 (p_i) 费用流的输入还是很好看出来的。
- 源点连每个点(1~n) 流量人数，费用零
- 每个点(1~n)连汇点，流量食物，费用零
【1】
这样问题就变成了源点到汇点的费用表示的概率最小了。都是题目的概率计数是乘法，而费用流中是加法。这里需要转化成log的形式log(ab) = log(a) + log(b) 这样结果最后求一个exp(x)就好了。
【2】
第二点，坏的概率你不知道具体是路径中那一条边坏了。如果把问题转化成最大的不坏的概率，就变成路径中每条路都不坏，那么概率就得以统一。
因此
对于u->v 容量c, 概率p
建边 u->v, 流量c， 费用-log(1-p)
ps:最大费用最大流和最小费用最大流的区别就是加边加个符号，结果反一下。
【3】
然后还有第三个问题：第一个人一定不会喷坏，那么我们拆边即可。这个相比前面反而是小问题了。
写的时候，代码spfa中有个地方没写EPS,TLE了不知道为什么，然后浮点费用流注意板子中int该改的要全改了。
代码
///2016ACM/ICPC亚洲区青岛站 Coding Contest 费用流
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-4;
struct MCMF {
static const int MAXN = 200;
static const int MAXM = 10000;
static const int INF = 1e9 + 7;
static const int INF0X3F = 0x3f3f3f3f;
int n, m, first[MAXN], s, t, sign;
double dist[MAXN];
int inq[MAXN], pre[MAXN], incf[MAXN];
int max_flow;
double min_cost;
struct Edge {
int to, cap, next;
double cost;
} edge[MAXM * 4];
void init(int l, int r, int ss, int tt) {
memset(first, -1, sizeof(first));
s = ss, t = tt, sign = 0;
max_flow = min_cost = 0;
}
void add_edge(int u, int v, int cap, double cost) {
edge[sign].to = v, edge[sign].cap = cap, edge[sign].cost = cost;
edge[sign].next = first[u], first[u] = sign++;
edge[sign].to = u, edge[sign].cap = 0, edge[sign].cost = -cost;
edge[sign].next = first[v], first[v] = sign++;
}
bool spfa(int s, int t) {
for(int i = 0; i < MAXN; i++ ) {
dist[i] = INF;
inq[i] = 0;
pre[i] = -1;
}
queue<int>que;
que.push(s), inq[s] = 1, dist[s] = 0;
incf[s] = INF0X3F;
while(!que.empty()) {
int now = que.front();
que.pop();
inq[now] = 0;
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, cap = edge[i].cap;
double cost = edge[i].cost;
///不加EPS T了？
if(cap > 0 && dist[to] > dist[now] + cost + EPS) {
dist[to] = dist[now] + cost;
incf[to] = min(incf[now], cap);
pre[to] = i;
if(!inq[to]) {
que.push(to);
inq[to] = 1;
}
}
}
}
return fabs(dist[t] - INF) > EPS;
}
void update(int s, int t) {
int x = t;
while(x != s) {
int pos = pre[x];
edge[pos].cap -= incf[t];
edge[pos ^ 1].cap += incf[t];
x = edge[pos ^ 1].to;
}
max_flow += incf[t];
min_cost += dist[t] * incf[t];
}
void minCostMaxFlow(int s, int t) {
while(spfa(s, t)) {
update(s, t);
}
}
} cwl;
int main() {
int t, n, m;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
cwl.init(0, n + 1, 0, n + 1);
for(int i = 1; i <= n; i++ ) {
int a, b;
scanf("%d %d", &a, &b);
if(a) {
cwl.add_edge(0, i, a, 0);
}
if(b) {
cwl.add_edge(i, n + 1, b, 0);
}
}
for(int i = 1; i <= m; i++ ) {
int u, v, cap;
double cost;
scanf("%d %d %d %lf", &u, &v, &cap, &cost);
cost = -log(1 - cost);
cwl.add_edge(u, v, 1, 0);
cwl.add_edge(u, v, cap - 1, cost);
}
cwl.minCostMaxFlow(0, n + 1);
printf("%.2f
", 1 - exp(-cwl.min_cost));
}
return 0;
}