洛谷 P3288 [SCOI2014]方伯伯运椰子

洛谷 P3288 [SCOI2014]方伯伯运椰子

题面

题意

给出一幅有向图,有一源点(仅一条边与之相连且这条边不可修改)和一汇点,每一条边有一个流量,单位流量所需费用,每额外增加单位流量所需费用和每减少一流量所需费用,给出的图保证所有所有边均满流,现在要修改一些边(改变流量),使修改后的所有边依然满流,且使修改后费用减少量除以修改流量之和的商最大.

做法

可以将问题转化,减少边的流量相当于退流,增加边的流量相当于增广,因为与源点相连的边不可修改,因此总流量不变,流量只是在边之间传递.
不难发现,如果对于u,v间的退流建边(u->v),u,v间的增广建边(v->u),那么图中的任意一个环都是一种合法的流量交换方法.
现在令答案为ans,因此ans>=(退流总费用X-增广总费用Y)/k,二分答案:
只要判断mid*k>=(X-Y)即可
k是修改总数,也就是环上边的总数,因此如果对所有边都减去mid,那么只需判断(X’-Y’)<=0,对原来的Y取反后就可转化为(X’+Y’)<=0就是负环.
单位退流的贡献:退流费用a-单位流量费用d.
单位增广的贡献:增广费用b+d.取反后为-b-d.
对增广费用取反,建图后,二分答案,每条边减去mid,若存在负环则答案合法.

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 5010
#define INF 0x3f3f3f3f
#define db double
using namespace std;int n,m,bb,T;
db l,r,mid,d[N];
struct Bn
{int from,to;db quan;
}bn[10010],tmp[10010];inline void add(int u,int v,int w)
{bb++;bn[bb].to=v;bn[bb].from=u;bn[bb].quan=(db)w;
}inline bool check(db u)
{int i,j;bool have;for(i=1;i<=bb;i++) tmp[i].quan+=u;d[1]=0;for(i=2;i<=n+2;i++) d[i]=INF;for(i=1;i<=n+2;i++){have=0;for(j=1;j<=bb;j++){if(d[tmp[j].to]>d[tmp[j].from]+tmp[j].quan){have=1;d[tmp[j].to]=d[tmp[j].from]+tmp[j].quan;}}if(!have) return 0;}return 1;
}int main()
{int i,j,p,q,o,a,b,c,d;cin>>n>>m;for(i=1;i<=m;i++){scanf("%d%d%d%d%d%d",&p,&q,&a,&b,&c,&d);if(c) add(q,p,a-d);add(p,q,b+d);}for(l=0,r=10000,T=200;T;T--){for(i=1;i<=bb;i++) tmp[i]=bn[i];mid=(l+r)/2;check(mid)?l=mid:r=mid;}printf("%.2lf",l);
}