HDU5988(最小费用流)

题意：图上有n个点，每个点上有a个人，b个面包，面包不够吃得去其他地方，但是每次走一条路，除了第一次，第二次开始都有P的概率让路坏掉。求路被破坏的最小概率。

分析：第一次没影响，那就对（流量-1）给花费即可。如果面包比人多，说明其他人能来这里吃，那么就把多余的连向源点。然后如果不够就把不够的连向汇点。

       难点：概率是乘法。没法算费用。但是如果同时取对数，那么就成加法了，就可以做了！细节看代码！

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const double eps=1e-9;
const int MAXN = 500+7;
const int inf = 1e9;
int n,m;
int s,e;
int cnt,head[MAXN];
struct node{int u,v,f,next;double w;} edge[20005];
void init()
{
    cnt=0;
    for(int i=0;i<=e;++i)head[i]=-1;
}
void add(int u,int v,int f,double w)
{
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].f=f;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].u=v;
    edge[cnt].v=u;
    edge[cnt].w=-w;
    edge[cnt].f=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
bool vis[MAXN];
double dis[MAXN];int pre[MAXN];
bool spfa()
{
    int i;
    for(i=0; i<=e; ++i)
    {
        dis[i]=inf;
        pre[i]=-1;
        vis[i]=0;
    }
    queue<int>q;
    q.push(s);
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(i=head[u]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            double w=edge[i].w;
            int f=edge[i].f;
            if(f>0&&dis[v]>dis[u]+w+eps)
            {
                dis[v]=dis[u]+w;
                pre[v]=i;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(pre[e]==-1)return 0;
    return 1;
}
double get_mincost()
{
    double max_flow=0,min_cost=0;
    while(spfa())
    {
        if(dis[e] < eps)break;
        int p=pre[e];
        int flow=inf;
        while(p!=-1)
        {
            flow=min(flow,edge[p].f);
            p=pre[edge[p].u];
        }
        max_flow+=flow;
        min_cost+=flow*dis[e];
        p=pre[e];
        while(p!=-1)
        {
            edge[p].f-=flow;
            edge[p^1].f+=flow;
            p=pre[edge[p].u];
        }
    }
    return min_cost;
}
int main()
{
    int tt;scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        s = 0;
        e = n+1;
        init();
        int a,b;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d",&a,&b);
            if(a>b)add(s,i,a-b,0);
            else if(b>a) add(i,e,b-a,0);
        }
        int u,v,w;double p;
        while(m--)
        {
            scanf("%d%d%d%lf",&u,&v,&w,&p);
            p=-log2(1-p);
            if(w>0)
                add(u,v,1,0.0);
            if(w-1>0)
                add(u,v,w-1,p);
        }
        double pp=get_mincost();
        pp=pow(2,-pp);
        printf("%.2lf\n",1-pp);
    }
    return 0;
}