题目链接

题意

有一张满流的DAG,其中起点只有一条出边,然后每条边有扩容和压缩的费用,还有单位运输量的费用,除了起点所连的边不能修改容量,其它的边都可以,问至少修改一条边,且最大流量不减少的情况下,$\frac{X-Y}{K}$最大是多少,其中X表示原来的运输费用,Y表示现在的运输费用+修改边容量的费用,K表示修改边容量的次数.
数据保证答案大于0

数据范围

1<=N<=5000
0<=M<=3000
1<=Ui,Vi<=N+2
0<=Ai,Bi<=500
0<=Ci<=10000
0<=Di<=1000

解法

由于式子里有除K的操作,可以思考分数规划:
将式子转变为
$X-Y==K*ans$
然后考虑原图本身就满流了,所以可以将压缩看成退流,扩容看成增广.又因为如果流量大于原来的流量,是一定不优的,所以最终的流量是固定的,而且每条边我们最多只会修改一次(这很重要).

然后建图,对于原图的一条边,如果它已经有流量就在新图中建一条反边,权值为$a-d$,然后每条原图中的边都要在新图中建一条方向相同,权值$b+d$的边.(这些权值都是因为我们每条边最多会修改一次,这些权值就是修改的代价).然后我们二分答案$ans$,在新图中给每条边的权值加上ans,看有没有负环,如果有,就说明$X-Y>K*ans$,不满足条件.

这个是因为每做一次调整,就相当于在新图上走了一条边,设边的权值为$w$所以$X-Y==X-(X+\sum w)==-\sum w$,所以如果新图上每条边都加上ans,后还会出现负环,说明
$-\sum w\gt k*ans$,最后记得以s为起点的那一条边不能被修改,在输入的时候判一下就可以了.

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+5;
const double eps=1e-4,inf=1e9;
inline int read(){char c=getchar();int t=0,f=1;while((!isdigit(c))&&(c!=EOF)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)&&(c!=EOF)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}return t*f;
}
int n,m,s,t;
struct edge{int v,p,w;
}e[maxn<<1];
int h[maxn],tot;
inline void add(int a,int b,int c){e[++tot].p=h[a];e[tot].v=b;e[tot].w=c;h[a]=tot;
}
int inq[maxn],cnt[maxn];
double dis[maxn];
bool spfa(double x){memset(inq,0,sizeof(inq));memset(cnt,0,sizeof(cnt));for(int i=1;i<=n;i++)dis[i]=inf;queue<int> q;while(!q.empty())q.pop();q.push(s);dis[s]=0;cnt[s]++;while(!q.empty()){int u=q.front();q.pop();inq[u]=0;for(int i=h[u];i;i=e[i].p){int v=e[i].v;double len=e[i].w+x;if(dis[v]>dis[u]+len){dis[v]=dis[u]+len;if(inq[v])continue;inq[v]=1;cnt[v]++;if(cnt[v]>n)return 1;q.push(v);}}}return 0;
}
int main(){//freopen("1.in","r",stdin);//freopen("1.out","w",stdout);n=read(),m=read();s=n+1,t=n+2;n+=2;double l=0,r=0;for(int i=1;i<=m;i++){int u=read(),v=read(),a=read(),b=read(),c=read(),d=read();if(u==n+1){s=v;continue;}if(c)add(v,u,a-d);add(u,v,b+d);if(a-d<0)r+=d-a;}double ans=0;while(r-l>=eps){double mid=(l+r)/2;if(spfa(mid)){ans=mid;l=mid;}else r=mid;}printf("%.2lf\n",ans);return 0;
}