欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2016青岛区域赛G题 Coding Contest 费用流

程序员文章站 2022-05-22 10:47:03
...

题意:给n个点,每个点上有x个人和y份食物,给m条边,每条边有走断的概率,不过第一次走是不会断的,点上的人可以通过边来移动,问你让所有人吃上饭破坏边的最小概率

思路:求破坏边的最小概率可以转换成不破坏边的最大概率,考虑到精度问题,我们通过对数运算把乘法转换成加法,设置一个超级源点和一个超级汇点,然后跑一遍最小费用最大流即可,注意使用eps精度修正

代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const double eps= 1e-8;
const int maxn=2e2+9;
struct Point {
    int x,y;//x代表人,y代表食物
}a[maxn];
struct node{
    int to,next,cap;
    double cost;
}edge[20009];
int s,t,n,cnt=0,vis[maxn],head[maxn],pre_id[maxn],pre_pt[maxn];
double dis[maxn];
double sum;
void add(int u,int v ,int cap,double cost){
    edge[cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].cap=cap;
    edge[cnt].cost=cost;
    head[u]=cnt++;
}
bool spfa(int s,int t){
   //cout<<n<<endl;
    for(int i=1;i<=n+1;i++){
        dis[i]=inf;
    }
    dis[s]=0.0;vis[s]=1;
    queue<int>q;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].to;
            if(edge[i].cap&&dis[v] >dis[u]+edge[i].cost+eps){
                dis[v]=edge[i].cost+dis[u];
                pre_pt[v]=u;
                pre_id[v]=i;
                if(vis[v])continue;
                q.push(v);
                vis[v]=1;
            }
        }
    }
    if(dis[t]==inf)return false;
    return true;
}
void EK(){
    while(spfa(s,t)){
        int Min=inf;
        for(int i=t;i!=s;i=pre_pt[i]){
            Min=min(Min,edge[pre_id[i]].cap);
        }
        for(int i=t;i!=s;i=pre_pt[i]){
            edge[pre_id[i]].cap-=Min;
            edge[pre_id[i]^1].cap+=Min;
        }
        sum+=(double)Min*dis[t];
    }
}
int main(){
    int i,j,k,m,tim;
    scanf("%d",&tim);
    while(tim--){
        cnt=0,sum=0;
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++){
            scanf("%d%d",&a[i].x,&a[i].y);
        }
        for(i=0;i<m;i++){
            int x,y,c;double p;
            scanf("%d%d%d%lf",&x,&y,&c,&p);
            p=-log2(1-p);
            if(c>0){
                add(x,y,1,0);
                add(y,x,0,0);
            }
            if(c-1>0){
                add(x,y,c-1,p);
                add(y,x,0,-p);
            }
        }
        s=0,t=n+1;
        for(i=1;i<=n;i++){
            if(a[i].x-a[i].y>0){
                add(s,i,a[i].x-a[i].y,0);
                add(i,s,0,0);
            }
            else{
                add(i,t,a[i].y-a[i].x,0);
                add(t,i,0,0);
            }
        }
        EK();
        //cout<<sum<<endl;
        double ans=1-pow(2,-sum);
        printf("%.2f\n",ans);
    }
}