Coding Contest(最小费用最大流)

题意：有n个点，每个点有一定数量的人和面包，对于每条边有容量c限制可以经过的人数，且在第二个人以后经过路径会有概率p破坏网络，问在所有人都拿到面包的情况下求网络破坏概率的最小值。

思路：因为最小费用最大流的应用问题为

给定网络D=(V,A,C) 每一条弧(vi,vj)上，除了已给容量Cij外，还给了一个单位流量的费用b(vi,vj)>=0. 所谓最小费用最大流问题就是求一个最大流f，使流的总输送费用最小。

很明显，这是一个最小费用最大流问题，对于建图，可以对于每个点，当人过量时，容量为过量的人数，且连接源点，当食物过量时，将容量变为过量的食物，且连接汇点，费用都为0。当对于边时，因为第一个人概率为0，所以对于一个人建一条费用为0的边，而剩下c-1的容量建立-log(1-p)，因为费用流是相加的，而概率是乘法，所以取对数，最后再转化回来。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define ll long long
using namespace std;
 
const int INF = 0x3f3f3f3f;
const int MAXN = 1007;
const int MAXM = 100007;
const double eps = 1e-8;
struct node
{
    double cost;
    int v,cap,next;
}edge[MAXM];
int ind,head[MAXN];
void add(int u, int v, int cap, double cost)
{
    edge[ind].v=v;
    edge[ind].cost=cost;
    edge[ind].cap=cap;
    edge[ind].next=head[u];
    head[u]=ind++;
    edge[ind].v=u;
    edge[ind].cost=-cost;
    edge[ind].cap=0;
    edge[ind].next=head[v];
    head[v]=ind++;
}
int pre[MAXN],m,n,N;
double dis[MAXN];
bool vis[MAXN];
bool SPFA(int s, int t)
{
    queue<int> q;
    for(int i=0; i<N; ++i)
    {
        dis[i]=INF;
        vis[i]=0;
        pre[i]=-1;
    }
    dis[s]=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=edge[i].next)
        {
            int v= edge[i].v;
            if(edge[i].cap>0 && dis[v]-dis[u]-edge[i].cost>eps)
            {
                dis[v]=dis[u]+edge[i].cost;
                pre[v]=i;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t]==-1)return 0;
    return 1;
}
double MinCostMaxFlow(int s, int t)
{
    int flow=0;
    double cost=0;
    while(SPFA(s,t))
    {
        int Min=INF;
        for(int i=pre[t]; i+1; i=pre[ edge[i^1].v ])
            if(Min>edge[i].cap)
            Min=edge[i].cap;
        for(int i=pre[t]; i+1; i=pre[ edge[i^1].v ])
        {
            edge[i].cap-=Min;
            edge[i^1].cap+=Min;
            cost+=edge[i].cost*1.0*Min;
        }
        flow+=Min;
    }
    return cost;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ind=0;
        memset(head,-1,sizeof(head));
        int a,b,c;
        double d;
        scanf("%d%d",&n,&m);
        N=n+2;
        for(int i=1; i<=n; ++i)
        {
            scanf("%d%d",&a,&b);
            int x=a-b;
            if(x>0)
                add(0,i,x,0);
            if(x<0)
                add(i,n+1,-x,0);
        }
        for(int i=0; i<m; ++i)
        {
            scanf("%d%d%d%lf",&a,&b,&c,&d);
            if(c>0)
                add(a,b,1,0);
            if(c-1>0)
                add(a,b,c-1,-log2(1.0-d));
        }
        double ans=1.0-pow(2,-MinCostMaxFlow(0,n+1));
        printf("%.2lf
",ans);
    }
    return 0;
}