HDU - 5988 Coding Contest (费用流)

Coding Contest

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4917    Accepted Submission(s): 1141

Problem Description

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 sicompetitors 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.

 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 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.

 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 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

0.50

Source

2016ACM/ICPC亚洲区青岛站-重现赛（感谢中国石油大学）

题意：n个点，每一个点有ai个人，bi包食物，m条边，每条边有一个容量ci，每一条边在被走完第一次后，再次走都有pi的概率被破坏，问n个人都能获得食物的同时，网络被破坏的最小概率

思路：很明显看出来这是一道最小费用最大流的题，我认为有两方面比较难想

1：求概率需要用乘法，费用流是费用相加的，我们可以给每个概率加一个log，这样就转化为相加了，但仅仅这样还不够，这样的话每条边的费用都是负数，是跑不出来正确答案的。就需要再次转化一下了，求网络被破坏的最小概率，就是求网格没被破坏的最大概率，所以费用log（1-p)，这样需要求出最大费用，再加一个负号就变成最小费用了，求出最小费用最大流ans，最后答案为1-exp（-ans）

2：当一条边第一次被走的时候是不会被破坏的，我们在建图的时候可以拆边，把每条边拆为2条，一条容量为w-1，费用为-log（1-p)，一条容量为1，费用为0，比较巧妙

剩下就是很常见的最小费用最大流的模型了

有一个大坑点是在跑最短路时，不加精度判断相等会T，不知道为什么

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
const double INF = 1e9;
const double eps = 1e-8;
struct Edge
{
	int from,to,cap,flow;
	double cost;
};
struct MCMF
{
	int n,m,s,t;
	vector<Edge> edges;
	vector<int> G[MAXN];
	int inq[MAXN];
	double d[MAXN];
	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.push_back((Edge){from,to,cap,0,cost});
		edges.push_back((Edge){to,from,0,0,-cost});
		m = edges.size();
		G[from].push_back(m - 2);
		G[to].push_back(m - 1);
	}
	bool BellmanFord(int s,int t,int &flow,double& cost)
	{
		for(int i = 0; i < n; i++) d[i] = INF;
		memset(inq,0,sizeof(inq));
		d[s] = 0.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] * (1.0 * a[t]);
		int u = t;
		while(u != s) {
			edges[p[u]].flow += a[t];
			edges[p[u] ^ 1].flow -= a[t];
			u = edges[p[u]].from;
		}
		return true;
	}
	double Mincost(int s,int t) {
		int flow = 0;
		double cost = 0.0;
		while(BellmanFord(s,t,flow,cost));
		return cost;
	}
}mcmf;
int main(void)
{
	int T,n,m;
	int s,e,a,b;
	int u,v;
	double cost;
	scanf("%d",&T);
	while(T--) {
		scanf("%d %d",&n,&m);
		s = 0,e = n + 1;
		mcmf.init(n + 2);
		for(int i = 1; i <= n; i++) {
			scanf("%d %d",&a,&b);
			mcmf.AddEdge(s,i,a,0.0);
			mcmf.AddEdge(i,e,b,0.0);
		}
		for(int i = 1; i <= m; i++) {
			scanf("%d %d %d %lf",&u,&v,&a,&cost);
			cost = -log(1 - cost);
			mcmf.AddEdge(u,v,1,0.0);
			mcmf.AddEdge(u,v,a - 1,cost);
		}
        double ans = -mcmf.Mincost(s,e);
		printf("%.2lf\n",1 - exp(ans));
	}
	return 0;
}