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

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

传送门

最大化 x − y k frac{x-y}{k} kx−y​

设函数 f ( r ) = r ∗ k + ( y − x ) f(r)=r*k+(y-x) f(r)=r∗k+(y−x)

不同的调整方案对应不同的直线

那么二分答案 m i d mid mid，做直线 x = m i d x=mid x=mid

若存在交点的 y y y座标小于零说明最优解在 m i d mid mid右边

否则在 m i d mid mid左边

满足最大流不变，且每条边满流

也就是压缩 x x x次，就需要扩容 x x x次，而且满足满流

那么对于边 ( u , v ) (u,v) (u,v)

u − > v u->v u−>v建边为扩容的费用,费用 b + d b+d b+d

v − > u v->u v−>u建边为压缩的费用,费用 a − d a-d a−d

这样一来,对于任意一条流,绕着这个环走一圈

把走过的边看作扩容和压缩,会发现仍然满足流量守恒

所以环就是可行的调整方案,而负环代表最优解在 m i d mid mid右边

注意 c c c为零的时候是不能连边的

#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);
}