首页 > 其他 > 详细

HDU5988 G - Coding Contest

时间:2021-03-05 09:58:03      阅读:26      评论:0      收藏:0      [点我收藏+]

太离谱了记一下
就费用是电线不坏的概率的乘积,然后用log把乘除变加减跑最小费用最大流就行
然后一直T,搞了两个小时发现要在spfa的比较那里加eps……

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N=10005;
const double eps=1e-8;
int T,n,m,s,t,h[N],cnt,fr[N];
double dis[N],ans;
bool v[N];
struct qwe
{
    int ne,no,to,va;
    double c;
}e[N<<1];
void add(int u,int v,int w,double c)
{
    cnt++;
    e[cnt].ne=h[u];
    e[cnt].no=u;
    e[cnt].to=v;
    e[cnt].va=w;
    e[cnt].c=c;
    h[u]=cnt;
}
void ins(int u,int v,int w,double c)
{
    add(u,v,w,c);
    add(v,u,0,-c);
}
bool spfa()
{
    memset(v,0,sizeof(v));
    for(int i=s;i<=t;i++)
        dis[i]=1e9;
    queue<int>q;
    dis[s]=0;
    v[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        v[u]=0;
        for(int i=h[u];i;i=e[i].ne)
            if(e[i].va>0&&dis[e[i].to]>dis[u]+e[i].c+eps)
            {
                dis[e[i].to]=dis[u]+e[i].c;
                fr[e[i].to]=i;
                if(!v[e[i].to])
                {
                    v[e[i].to]=1;
                    q.push(e[i].to);
                }
            }
    }
    return dis[t]<1e9;
}
void mcf()
{//cout<<"OK"<<endl;
    int x=1e9;
    for(int i=fr[t];i;i=fr[e[i].no])
        x=min(x,e[i].va);
    for(int i=fr[t];i;i=fr[e[i].no])
    {
        e[i].va-=x;
        e[i^1].va+=x;
        ans+=x*e[i].c;
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(h,0,sizeof(h));
        scanf("%d%d",&n,&m);
        cnt=1,s=0,t=n+1,ans=0;
        for(int i=1,x,y;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            if(x>y)
                ins(s,i,x-y,0);
            else if(y>x)
                ins(i,t,y-x,0);
        }
        for(int i=1,x,y,z;i<=m;i++)
        {
            double no;
            scanf("%d%d%d%lf",&x,&y,&z,&no);
            if(z>0)
                ins(x,y,z-1,-log2(1-no)),ins(x,y,1,0);
        }
        while(spfa())
            mcf();
        printf("%.2lf\n",1.0-pow(2,-ans));
    }
    return 0;
}

HDU5988 G - Coding Contest

原文:https://www.cnblogs.com/diakla/p/14483858.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!