hdu 5988 Coding Contest(最小费用流 骚)

题意:给n个点与m条单向路。每个点有si的人与bi的食物。每条路给定ui , vi , ci and pi 分别表示起点、终点、流量、碰断线的概率。

每条单向路在第一个人走的时候碰断线的概率为0，第2、3…人走碰断线的概率为pi。

问在保证所有人每人能吃到一份食物的前提下，有人碰断线的最小概率是多少?

骚操作：1 因为第一个人碰线概率为0 所以将路径上的流量分出来一条边 代价为0

骚操作：2 将乘积取对数 就可以相加 从而转化为 模板

骚操作：3 因为涉及浮点数 所以加eps修正 不在直接T到死

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;
typedef long long LL ;
const int inf = 0x3f3f3f3f;
const int N = 110;
const double eps = 1e-7;
int a[N], b[N];
struct node
{
    int to, next, cap;
    double d;
}p[1000000];
int head[N], cnt;
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
    return ;
}
void add(int u,int v,int cap,double d)
{
    p[cnt].to=v,p[cnt].cap=cap,p[cnt].next=head[u],p[cnt].d=d;head[u]=cnt++;
    p[cnt].to=u,p[cnt].cap=0,p[cnt].next=head[v],p[cnt].d=-d;head[v]=cnt++;
    return ;
}
queue<int>q;
int vis[N], pre[N];
double dist[N];
int spfa(int s,int t)
{
    for(int i=s;i<=t;i++) vis[i]=0,dist[i]=inf,pre[i]=-1;
    while(!q.empty()) q.pop();
    dist[s]=0.0,vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=p[i].next)
        {
            int v=p[i].to;
            if(p[i].cap>0&&dist[v]>dist[u]+p[i].d+eps)
            {
                pre[v]=i;
                dist[v]=dist[u]+p[i].d+eps;
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
    return dist[t]!=inf;
}
double min_cost(int s,int t)
{
    double cost=0;
    while(spfa(s,t))
    {
        int flow=inf;
        for(int i=pre[t];i!=-1;i=pre[p[i^1].to]) flow=min(flow,p[i].cap);
        for(int i=pre[t];i!=-1;i=pre[p[i^1].to]) p[i].cap-=flow,p[i^1].cap+=flow;
        cost+=(1.0)*flow*dist[t];
    }
    return cost;
}

int main()
{
    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        init();
        int s=0, e=n+1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d", &a[i], &b[i]);
            if(a[i]>b[i]) add(s,i,a[i]-b[i],0);
            else if(a[i]<b[i]) add(i,e,b[i]-a[i],0);
        }
        for(int i=0;i<m;i++)
        {
            int u,v,cap;
            double px;
            scanf("%d %d %d %lf",&u,&v,&cap,&px);
            double ph=-log2(1-px);
            if(cap>0) add(u,v,1,0);
            if(cap>1) add(u,v,cap-1,ph);
        }
        double sum=-min_cost(s,e);
        sum=pow(2,sum);
        printf("%.2f\n",1-sum);
    }
    return 0;
}