G - Coding Contest HDU - 5988

叁歲伎倆 2023-07-03 10:53 13阅读 0赞

看到题意，求最小概率，同时每条边都有限制。那岂不是最大流量最小费用。但是这里的概率是相乘，我们用最大流量最小费用的时候概率是相加。我们可以取log  
同时，注意到，求最小概率，就为1-最大概率。故，我们把每条边的概率赋值为1-最小概率  
例log（ab） =log(a)+log(b)。  
但是又有一个问题，取完log后的值为负数，所以我们要把负数\*-1变成正数。  
因为负数的最大费用=变为正数后的最小费用。

#include <bits/stdc++.h>
    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 ++){
                int a,b;
                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 = 1; i <= m; i ++)
            {
                int a,b,c; double x;
                scanf("%d%d%d%lf",&a,&b,&c,&x);
                if(c > 0) add(a,b,1,0);
                if(c - 1 > 0) add(a,b,c - 1,-log2(1.0 - x));
            }
            double ans=1.0-pow(2,-MinCostMaxFlow(0,n+1));
            printf("%.2f\n",ans);
        }
        return 0;
    }