CF653D Delivery Bears题解

· · 题解

CF653D Delivery Bears

::anti-ai[]

::anti-ai[]

卡精度，一点也不清新/fn

思路

二分每个熊搬运的货物重量 mid，假设一条边的承重上限为 w，则这条边至多经过 \left \lfloor \frac{w}{mid} \right \rfloor 只熊。我们希望 x 头熊从 1 走到 n，这不就是最大流吗？以 1 为源点 n 为汇点跑最大流即可。

代码

网络流使用的 ISAP 实现，非常优秀。

#include<bits/stdc++.h>
using namespace std;
int n,m,num,cnt=1,to[1005],nxt[1005],w[1005],ww[1005];
int tp[55],dep[55],h[55],gap[55];
void add(int x,int y,int z){to[++cnt]=y,w[cnt]=ww[cnt]=z,nxt[cnt]=tp[x],tp[x]=cnt;}
void bfs()
{
    for(int i=1;i<=n;i++) dep[i]=n,h[i]=tp[i],gap[i]=0;
    queue<int> q; 
    dep[n]=0,q.push(n);
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i=tp[t];i;i=nxt[i])
            if(i%2&&dep[to[i]]==n) dep[to[i]]=dep[t]+1,q.push(to[i]);
    }
    for(int i=1;i<=n;i++) gap[dep[i]]++;
}
int dfs(int x,int y)
{
    if(x==n||!y) return y;
    int f=0;
    for(int i=h[x];i;i=nxt[i])
    {
        h[x]=i;
        if(dep[to[i]]+1==dep[x])
        {
            int p=dfs(to[i],min(y-f,w[i]));
            f+=p,w[i]-=p,w[i^1]+=p;
        }
        if(dep[1]==n||f>=y) return f;
    }
    if(!--gap[dep[x]]) 
    {
        dep[1]=n;
        return f;
    }
    gap[++dep[x]]++,h[x]=tp[x];
    return f;
}
bool ISAP()
{
    bfs();
    int f=num;
    while(dep[1]!=n&&f>0) f-=dfs(1,f);
    return !f; 
}
bool check(long double &x)
{
    for(int i=1;i<=cnt;i++) w[i]=min(ww[i]/x,(long double)num);
    return ISAP();
}
int main()
{
    scanf("%d%d%d",&n,&m,&num);
    long double l=0,r=0;
    while(m--)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,0),r=max(r,(long double)w);
    }
    for(int i=1;i<=60;i++)
    {
        long double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.13Lf",l*num);
    return 0;
}