题目
题目描述
四川的方伯伯为了致富，决定引进海南的椰子树。方伯伯的椰子园十分现代化，椰子园中有一套独特的交通系统。
现在用点来表示交通节点，边来表示道路。这样，方伯伯的椰子园就可以看作一个有n+2个交通节点，m条边的有向无环图。n+1号点为入口，n+2号点为出口。
每条道路都有6个参数，ui，vi，ai，bi，ci，di，
分别表示，该道路从ui号点通向vi号点，将它的容量压缩一次要ai的花费，容量扩大一次要bi的花费，该条道路当前的运输容量上限为ci，并且每单位运输量通过该道路要di的费用。
在这个交通网络中，只有一条道路与起点相连。因为弄坏了这条道路就会导致整个交通网络瘫痪，聪明的方伯伯决定绝不对这条道路进行调整，也就是说，现在除了这条道路之外，对其余道路都可以进行调整。
有两种调整方式：
选择一条道路，将其进行一次压缩，这条道路的容量会下降1单位。
选择一条道路，将其进行一次扩容，这条道路的容量会上升1单位。
一条道路可以被多次调整。
由于很久以前，方伯伯就请过一个工程师，对这个交通网络进行过一次大的优化调整。所以现在所有的道路都被完全的利用起来了，即每条道路的负荷都是满的（每条道路的流量等于其容量）。
但方伯伯一想到自己的海南椰子会大丰收，就十分担心巨大的运输量下，会导致过多的花费。因此，方伯伯决定至少进行一次调整，调整之后，必须要保持每条道路满负荷，且总交通量不会减少。
设调整后的总费用是Y，调整之前的总费用是X。现在方伯伯想知道，最优调整比率是多少，即假设他进行了k次调整，(X-Y)/k最大能是多少？
注：总费用=交通网络的运输花费+调整的花费
输入输出格式
输入格式：
第一行包含二个整数N，M接下来M行代表M条边，表示这个交通网络每行六个整数，表示Ui,Vi,Ai,Bi,Ci,Di接下来一行包含一条边，表示连接起点的边
输出格式：
一个浮点数，保留二位小数。表示答案，数据保证答案大于0
输入输出样例
输入样例#1：
5 10
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22
输出样例#1：
103.00
说明
1<=n<=5000，0<=m<=3000，1<=ui,vi<=n+2，0<=ai,bi<=500，0<=ci<=10000,0<=di<=1000
题解
感谢$fuge$帮我理解了最后一步
这题神TM标签网络流似乎用到了网络流的思想……
首先，这题肯定是分数规划，因为ta要求调整之后必须要保持每条道路满负荷，且总交通量不会减少
如果总交通量增加，花费肯定会增加，即大于调整前的花费
所以要保持流量不变，我们考虑网络流的思想
压缩$\rightarrow$网络流里的退流
扩充$\rightarrow$网络流里的增广
所以对于原图给定每一条边$(u,v)$，我们在新图里对应建两条边
$(v,u)$，边权为$a_i-d_i$（你压缩一单位花费$a_i$，同时这条边少了一单位流量所以花费减去$d_i$），对应压缩
$(u,v)$，边权为$b_i+d_i$（你扩充一单位花费$b_i$，同时这条边多了一单位流量所以花费加上$d_i$），对应扩充
我们令$tot=max(\frac{X-Y}{k})$，所以$tot\ge \frac{X-Y}{k}$
即$tot\times k\ge X-Y$
所以我们二分一个数$mid$，即调整比率
我们可以发现，在新图中xjb跑，经过的点数（也是边数）就是调整次数，即$k$
因为你调整一次就相当于经过新图里的一条边，同时加上这条边的贡献$w$（就是边权）
我们可以把$X-Y$化为$X-(X+\sum w)$，即$-\sum w$
所以问题就转为了比较$mid\times k$和$-\sum w$的大小
即$mid\times k+\sum w$是否大于0
然后原问题就转化为在新图里找负环
要是有负环，说明$mid\times k<X-Y$
反之说明$mid\times k\ge X-Y$
这样问题就解决了
还有一点，题目中要求不调整源点连接的那一条边，所以特判一下但没特判好像也能过
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
using namespace std;
const int MAX=1e4+1;
const double ops=1e-3;
struct p{
int x,y;
double dis;
}c[MAX];
int n,m,num;
int h[MAX];
double d[MAX];
bool use[MAX];
int read()
{
int x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y,double dis)
{
c[++num]=(p){h[x],y,dis},h[x]=num;
}
bool spfa(int x,double mid)
{
use[x]=1;
for(int i=h[x];i;i=c[i].x)
if(d[c[i].y]>d[x]+c[i].dis+mid)
{
d[c[i].y]=d[x]+c[i].dis+mid;
if(use[c[i].y]) return 1;
if(spfa(c[i].y,mid)) return 1;
}
use[x]=0;
return 0;
}
bool look(double mid)
{
memset(d,0,sizeof(d));
memset(use,0,sizeof(use));
for(int i=1;i<=n+2;i++)
if(spfa(i,mid)) return 1;
return 0;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
double A=read(),B=read(),dis=read(),cn=read();
if(x==n+1) A=0,B=0,cn=0;
if(dis) add(y,x,A-cn);
add(x,y,B+cn);
}
double l=0,r=1e8,ans;
while(l<=r)
{
double mid=(l+r)/2;
if(look(mid))
ans=mid,l=mid+ops;
else r=mid-ops;
}
printf("%.2lf",ans);
return 0;
}
