HDU5988 Coding Contest 【最小费用最大流】【2016ACM/ICPC亚洲区青岛站】

题意：

给出n个点和m条边，每个点有si个人，bi份食物,每条边一开始可以通过一个人,后来的人每通过一个就有pi的概率使整个系统崩溃,问崩溃的最小的概率是多少

思路：

对于崩溃的最小概率，由于只有一条奔溃就会全部崩溃，那么将所有不会崩溃的概率相乘就是不会奔溃的概率，所以崩溃的概率 = 1 - 不会崩溃的概率，所以要求最大不会崩溃的概率，那么我们只要对不会崩溃的概率取反即可
一开始想到了网络流，但是对于概率相乘不知道如何处理，然后学到了一个公式：
$log\left(a\right)+log\left(b\right)+log\left(c\right)==log(a\ast b\ast c)$log(a)+log(b)+log(c)==log(a∗b∗c)
所以费用为 $-log(1-p_i)$−log(1−pi​)
由于点从1到n，于是我们可以建立一个以0为源点，以n+1为汇点的图。
每个区域如果有食物和人，那么人先吃掉食物是最优的。
如果食物过量的点，我们可以建一条边从源点到该点，容量是过量的食物数量，费用是0；
如果人数过量的点，我们可以建一条边从该点到汇点，容量是过量的人数，费用是0。
剩下的就是图中的m条边，对于每条边分解成两条边，为：
从u到v，容量是1，费用是0；从u到v，容量是cap-1，费用为 $-log(1-p_i)$−log(1−pi​)
据此，跑一遍最小费用最大流即可

我用的是kuangbin的SPFA的模板，一开始T了一发，不会图论，想不明白为什么会T
于是套了zkw费用流板子

AC_code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXM = 20000;
const int INF = 0x3f3f3f3f;
struct Edge {
	int to,next,cap,flow;
	double cost;
	Edge(int _to = 0,int _next = 0,int _cap = 0,int _flow = 0,double _cost = 0):
		to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost) {}
} edge[MAXM];
struct ZKW_MinCostMaxFlow {
	int head[MAXN],tot;
	int cur[MAXN];
	double dis[MAXN];
	bool vis[MAXN];
	int ss,tt,N;//源点、汇点和点的总个数（编号是 0～N-1）, 不需要额外赋值，调用会直接赋值
	int  max_flow;
	double min_cost;
	void init() {
		tot = 0;
		memset(head, -1,sizeof(head));
	}
	void addedge(int u,int v,int cap,double cost) {
		edge[tot] = Edge(v,head[u],cap,0,cost);
		head[u] = tot++;
		edge[tot] = Edge(u,head[v],0,0, -cost);
		head[v] = tot++;
	}
	int aug(int u,int flow) {
		if(u == tt)return flow;
		vis[u] = true;
		for(int i = cur[u]; i != -1; i = edge[i].next) {
			int v = edge[i].to;
			if(edge[i].cap > edge[i].flow && !vis[v] && dis[u] ==dis[v] + edge[i].cost) {
				int tmp = aug(v,min(flow,edge[i].cap - edge[i].flow));
				edge[i].flow += tmp;
				edge[i^1].flow -= tmp;
				cur[u] = i;
				if(tmp)return tmp;
			}
		}
		return 0;
	}
	bool modify_label() {
		double d = INF;
		for(int u = 0; u < N; u++)
			if(vis[u])
				for(int i = head[u]; i != -1; i = edge[i].next) {
					int v = edge[i].to;
					if(edge[i].cap>edge[i].flow && !vis[v])
						d = min(d, dis[v]+edge[i].cost - dis[u]);
				}
		if(d == INF)return false;
		for(int i = 0; i < N; i++)
			if(vis[i]) {
				vis[i] = false;
				dis[i] += d;
			}
		return true;
	}
	/* * 直接调用获取最小费用和最大流 * 输入: start-源点，end-汇点，n-点的总个数（编号从 0 开始） * 返回值: pair<int,int> 第一个是最小费用，第二个是最大流 */
	pair<double,int> mincostmaxflow(int start,int end,int n) {
		ss = start, tt = end, N = n;
		min_cost = max_flow = 0;
		for(int i = 0; i < n; i++)dis[i] = 0;
		while(1) {
			for(int i = 0; i < n; i++)cur[i] = head[i];
			while(1) {
				for(int i = 0; i < n; i++)vis[i] = false;
				int tmp = aug(ss,INF);
				if(tmp == 0)break;
				max_flow += tmp;
				min_cost += tmp*dis[ss];
			}
			if(!modify_label())break;
		}
		return make_pair(min_cost,max_flow);
	}
} solve;

int main() {
	int t, n, m, a, b, u, v, cap;
	double cost;
	scanf("%d", &t);
	while(t--)	{
		scanf("%d %d", &n, &m);
		solve.init();//n个点 + 源点0 + 汇点 n+1
		for(int i = 1; i <= n; i++) {
			scanf("%d %d", &a, &b);
			a -= min(a, b);
			b -= min(a, b);
			if(a > 0) {
				solve.addedge(0, i, a, 0);
			} else {
				solve.addedge(i, n+1, b, 0);
			}
		}
		for(int i = 1; i <= m; i++) {
			scanf("%d %d %d %lf", &u, &v, &cap, &cost);
			if(cap > 0) {
				solve.addedge(u, v, 1, 0);
			}
			if(cap-1 > 0) {
				solve.addedge(u, v, cap-1, -1*log(1.0-cost));
			}
		}
		pair<double, int> ans = solve.mincostmaxflow(0, n+1, n+1);
		double q = ans.first;
		q = 1.0 - exp(-1.0*q);
		printf("%.2lf\n", q);
	}

	return 0;
}