题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5988
题目大意：
给定n个点，m条有向边，每个点是一个吃饭的地方，每个人一盒饭。每个点有S个人，有B盒饭。每条边只能被走c次，每条边上都有电线，
第一个人通过的时候，不会破坏电线，从第二个人开始，每次都有概率p破坏掉电线。使得每个人都能吃饭，求最小破坏电线的概率。
解题思路：
题目要求我们求最小破坏电线的概率，就是一个最小乘积问题，加上log可以将其转变为加法，那样就可以使用费用刘来解决了。
按以下方式建图：
①源点st向第i个人建边，流量为S。
②第i个人向汇点建边，流量为B。
③u->v连边，流量为c，花费为-log(1-p)。
然后跑费用流，1-exp(-cost)即为答案。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define LL long long
#define pii pair<double,int>
#define pll pair<long long,long long>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define bug cout<<"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"<<endl;
#define bugc(_) cout << (#_) << " = " << (_) << endl;
using namespace std;
const double eps=1e-;
const int N=1e2+;
const int M=1e5+;
const int INF=0x3f3f3f3f; struct node{
int to,next,flow;
double cost;
}edge[M*]; int cnt,st,en,n,m;
int head[N],pre[N];
double dis[N];//dis[i]表示到dis[i]为止不破坏电线的最大概率
bool vis[N]; int sgn(double x) { return x < -eps? -: x > eps; } void init(){
cnt=;
memset(head,,sizeof(head));
} void link(int u,int v,int flow,double cost){
edge[cnt]=node{v,head[u],flow,cost};
head[u]=cnt++;
edge[cnt]=node{u,head[v],,-cost};
head[v]=cnt++;
} bool spfa() {
memset(pre,,sizeof(pre));
memset(vis,false,sizeof(vis));
for(int i=st;i<=en;i++) dis[i]=INF;
dis[st]=;
queue<int>q;
q.push(st);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i;i=edge[i].next){
node t=edge[i];
if(t.flow&&dis[t.to]>dis[u]+t.cost+eps){
dis[t.to]=dis[u]+t.cost;
pre[t.to]=i;
if(!vis[t.to]){
vis[t.to]=true;
q.push(t.to);
}
}
}
}
if(dis[en]==INF)
return false;
return true;
} void mcmf(int &flow,double &cost){
while(spfa()){
int mmin=INF;
for(int i=pre[en];i;i=pre[edge[i^].to]){
mmin=min(mmin,edge[i].flow);
}
for(int i=pre[en];i;i=pre[edge[i^].to]){
edge[i].flow-=mmin;
edge[i^].flow+=mmin;
cost+=edge[i].cost*mmin;
}
flow+=mmin;
}
} int main(){
int T;
scanf("%d",&T);
while(T--){
init();
int n,m;
scanf("%d%d",&n,&m);
st=,en=n+;
for(int i=;i<=n;i++){
int s,b;
scanf("%d%d",&s,&b);
if(s-b>) link(st,i,s-b,);
if(s-b<) link(i,en,b-s,);
}
for(int i=;i<=m;i++){
int u,v,flow;
double p;
scanf("%d%d%d%lf",&u,&v,&flow,&p);
p=-log(-p);
if(flow>) link(u,v,,);
if(flow>) link(u,v,flow-,p);
}
int flow=;
double cost=;
mcmf(flow,cost);
cost=exp(-cost);
printf("%.2f\n",-cost);
}
return ;
}