hdu5988（费用流，对数相乘做加法）

题意：一个网络流的图，有n个点，从1~n，然后m条边，每个点有两个值，一个是人的数量si一个是饭的数量bi。每条m边有容量ci，还有走上去可能踩断电线的概率pi第一次踩上去没有事，之后都要p概率)。问让所有人吃到饭的前提下断电线的最小概率是多少。

解法：每条边有走的次数（流量），每条边走一次发生破坏概率为p（流量1，费用p），容易想到费用流。可是费用流往往是费用相加的，这个是概率，只能相乘。有什么办法，log函数可以把乘除法转换为加减法。所以对每个概率取个log当成费用就行了。

注意，这个概率是踩坏的概率，你数学思维一下，求总的踩坏概率不可能会是说全部都是踩坏的概率相乘吧，我也可以有一些边是可以吧被拆坏，所以我们需要求对立面

这时候就应该从反方向进行考虑，求踩坏的最小概率，就是求不踩坏的最大概率，1-p后取log，和以上同理，求出了最大费用。取出来还回去后用1减一下就好了。

新建源点s，汇点t，对于S>B的需要人走，从源点连一条流量为S[i]-B[i]，费用为0出门不需要费用)的边过去，adds,i,S[i]-B[i],0)，对于s<b的，addi,t,B[i]-S[i],0)。

为什么要这样建边呢，是因为从源点s出来的人要到汇点t去，到汇点的边就相当于到这个点的一些人吃了面包走到了汇点。

然后还有一个问题，就是第一次踩的时候，不会触发，那么从原有的边中取一条出来，流量1，费用0就好了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=200;
const int INF =0x3f3f3f3f;
const double esp=1e-8;
struct Edge
{
    int from,to,cap,flow; double cost;
    Edgeint u,int v,int ca,int f,double co):fromu),tov),capca),flowf),costco){};
};

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 initint n)//初始化
    {
        this->n=n;
        forint i=0;i<=n;i++)
            G[i].clear);
        edges.clear);
    }

    void AddEdgeint from,int to,int cap,double cost)//加边
    {
        edges.push_backEdgefrom,to,cap,0,cost));
        edges.push_backEdgeto,from,0,0,-cost));
        int m=edges.size);
        G[from].push_backm-2);
        G[to].push_backm-1);
    }

    bool SPFAint s,int t,int &flow,double &cost)//寻找最小费用的增广路，使用引用同时修改原flow,cost
    {
        forint i=0;i<n;i++)
            d[i]=INF;
        memsetinq,0,sizeofinq));
        d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;
        queue<int> Q;
        Q.pushs);
        while!Q.empty))
        {
            int u=Q.front);
            Q.pop);
            inq[u]--;
            forint i=0;i<G[u].size);i++)
            {
                Edge& e=edges[G[u][i]];
                ife.cap>e.flow && d[e.to]-d[u]-e.cost>esp)//满足可增广且可变短
                {
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=mina[u],e.cap-e.flow);
                    if!inq[e.to])
                    {
                        inq[e.to]++;
                        Q.pushe.to);
                    }
                }
            }
        }
        ifd[t]==INF) return false;//汇点不可达则退出
        flow+=a[t];
        cost+=d[t]*a[t];
        int u=t;
        whileu!=s)//更新正向边和反向边
        {
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
            u=edges[p[u]].from;
        }
        return true;
    }

    double MincotMaxflowint s,int t)
    {
        int flow=0;
        double cost=0;
        whileSPFAs,t,flow,cost));
        return cost;
    }
}MM;
int main){
    int _;scanf"%d",&_);
    while_--){
        int n,m;
        scanf"%d%d",&n,&m);
        MM.initn+2);
        forint i=1;i<=n;i++){
            int s,b; scanf"%d%d",&s,&b);
            int T=s-b;
            ifT>0) MM.AddEdge0,i,s-b,0);
            else ifT<0) MM.AddEdgei,n+1,b-s,0);
        }
        forint i=1;i<=m;i++){
            int u,v,c;double p;
            scanf"%d%d%d%lf",&u,&v,&c,&p);
            p=-log21.0-p);///求最大不被破坏->最小被破坏
            ifc>0)
                MM.AddEdgeu,v,1,0);
            ifc-1>0)
                MM.AddEdgeu,v,c-1,p);
        }
        double ans=MM.MincotMaxflow0,n+1);
        ans=1-pow2,-ans);
        printf"%.2f
",ans);

    }
}

View Code