本文共 1928 字，大约阅读时间需要 6 分钟。

方伯伯在一个DAG上跑网络流

因为我们不能减少交通量,那肯定也不会去可以增加交通量(不划算,因为要多交运费)

所以能做的调整就是把一些流量扩充到另一些边去

扩容的方式大概是这样:比如现在从源点到汇点有两条路径$A,B$

那么我们可以让$A$路径流量整体加一,让$B$路径的流量整体减一,这样仍然流量守恒

不过答案可能就会发生变化了。

然而,直接去考虑$DAG$的所有路径不太好搞

我们把扩容当作正向边,把压缩看成反向边

这样图中的每个环都相当于一个替换流量的方案!!

再考虑答案的计算方式为$\frac{val}{k}$(其中$val$为省下来的钱,$k$是调整次数)

很明显这是一个$01$分数规划的形式,设$f(r)=k\ast r-val$

每个环对应一条直线,我们二分答案$mid$

每次看一下是否有直线的$f(mid)$小于零

有的话,答案还可以往右边二分,否则往左边二分

第$i$条边的边权看作$mid+va{l}_i$即可,找负环.

#include 
   
    using namespace std;const double eps = 1e-7;const int maxn = 2e6+10;const int inf = 1e9+10;struct edge{
       int to,nxt; double w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,double w){
       d[++cnt]=(edge){
   v,head[u],w},head[u]=cnt;}double dis[maxn];int vis[maxn],num[maxn],n,m;bool spfa(double mid){
       queue
    
     q;    for(int i=0;i<=n+2;i++)   dis[i]=inf,vis[i]=0,num[i]=0;    dis[0]=0,num[0]=1;    q.push(0);    while( !q.empty() )    {
           int u=q.front(); q.pop();        vis[u]=0;        for(int i=head[u];i;i=d[i].nxt )        {
               int v=d[i].to;            double val = mid+d[i].w;            if( dis[v]>dis[u]+val )            {
                   dis[v]=dis[u]+val;                if( !vis[v])                {
                   	num[v]++;                    if( num[v]>=n ) return true;                    vis[v]=1,q.push(v);                }            }        }    }    return false;}int main(){
       cin >> n >> m;    for(int i=1;i<=m;i++)    {
           int u,v,a,b,c,d;        cin >> u >> v >> a >> b >> c >> d;        if( c ) add(v,u,a-d);        add(u,v,b+d);    }    for(int i=1;i<=n+2;i++)	add(0,i,0);    double l=0,r=1000000,mid,ans;    while( r>=l+eps )    {
           mid = (l+r)/2.0;        if( spfa(mid) ) l=mid+eps,ans=mid;        else r=mid-eps;    }    printf("%.2lf",ans);}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115440545 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！