P3288 [SCOI2014]方伯伯运椰子(流量守恒,分数规划)

P3288 [SCOI2014]方伯伯运椰子(流量守恒,分数规划)

LINK

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

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

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

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

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

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

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

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

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

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

很明显这是一个 01 01 01分数规划的形式,设 f ( r ) = k ∗ r − v a l f(r)=k*r-val f(r)=k∗r−val

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

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

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

第 i i i条边的边权看作 m i d + v a l i mid+val_i mid+vali​即可,找负环.

#include <bits/stdc++.h>
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<int>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);
}