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

题意:给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);
    }
}