# HDU 5988 Coding Contest （最小费用流）

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

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


## 思路

PS: 这道题目卡常好严重，貌似 1000ms 的题目 998ms 过的。

So ，如果 TLE 可以考虑再提交一下。

## AC 代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 105;
const int maxm = 21000;
const int INF = 2e9;
const double eps = 1e-8;

struct edge
{
int to;     //边终点
int next;   //下一个兄弟位置
int cap;    //容量
int flow;   //流量
double cost;   //费用
} edge[maxm];

int pre[maxn];
double dis[maxn];
int N;  //节点总个数
bool vis[maxn];

int person[maxn],thing[maxn];

void init(int n)
{
N=n;
tol=0;
}

void addedge(int u,int v,int cap,double cost)  //同时增加原边与反向边
{
edge[tol].to=v;
edge[tol].cap=cap;
edge[tol].cost=cost;
edge[tol].flow=0;
edge[tol].to=u;
edge[tol].cap=0;
edge[tol].cost=-cost;
edge[tol].flow=0;
}

/*
* SPFA 算法判断是否存在s到t的通路
*/
bool spfa(int s,int t)
{
queue<int>q;
for(int i=0; i<N; i++)
{
dis[i]=INF;
vis[i]=false;
pre[i]=-1;
}
dis[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=false;
{
int v=edge[i].to;
if(edge[i].cap>edge[i].flow&&dis[v]-dis[u]-edge[i].cost>eps)    //如果可以松弛该点
{
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if(!vis[v]) //如果该点不在队列中，入队
{
vis[v]=true;
q.push(v);
}
}
}
}
return (pre[t]!=-1);    //返回是否s到t是否有路径
}

/*
* int s 起点
* int t 终点
*/
int minCostMaxFlow(int s,int t,double &cost)
{
int flow=0;
while(spfa(s,t))
{
int minn=INF;   //当前路径可增广值
for(int i=pre[t]; i!=-1; i=pre[edge[i^1].to])   //因为建图时每增加一条边会同时加入它的反向边，因此i^1为找出与i刚好相反的部分
{
if(minn>edge[i].cap-edge[i].flow)
minn=edge[i].cap-edge[i].flow;
}
for(int i=pre[t]; i!=-1; i=pre[edge[i^1].to])   //修改图，计算花费
{
edge[i].flow+=minn;
edge[i^1].flow-=minn;
cost+=edge[i].cost*minn;
}
flow+=minn;
}
return flow;
}

int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n=0,m=0;
scanf("%d%d",&n,&m);
init(n+2);
for(int i=1; i<=n; i++)
{
scanf("%d%d",person+i,thing+i);
person[i]-=thing[i];
}
for(int i=0; i<m; i++)
{
int u=0,v=0,cap=0;
double p;
scanf("%d%d%d%lf",&u,&v,&cap,&p);
p = -log2(1.0-p);
if(cap>1)
if(cap>0)
}
for(int i=1; i<=n; i++)
{
if(person[i]>0)