题目大意:
题解:
可以发现,如果对一条边扩充容量那么费用将会增加(b+d)
如果对一条边减少容量那么费用将会增加(a-d)
但是我们发现:和增加容量不同,减少容量是有限制的
但是由于我们求的是一个最优比率,所以其实只要c不是零,我们就不用管
至于为什么不用管呢...后面再说。
然后我们依据上面的费用关系构造新图,新图的边不变,边权是之前在原图中扩充后增加的费用.然后再对每个容量不为0的原图的边添加一条表示减少流量的反边,边权自然就是减少容量增加的费用。
然后我们根据消圈定理可得:只要图中存在负环,那么就有更优解。
所以其实我们现在是在这张新图上找一个最优比率负环。
并且我们只需要对这条负环上的边只调整一次即可做到最优化比率
所以原来的容量是几都没有关系,大于1即可
所以转化成了一个01分数规划问题,直接求即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 5010;
const int maxm = 3010;
const double eps = 1e-9;
struct Edge{
int to,next;
double dis;
}G[maxm<<1];
int head[maxn],cnt;
void add(int u,int v,double d){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
G[cnt].dis = d;
}
bool inq[maxn];
double dis[maxn];
#define v G[i].to
bool dfs(int u){
inq[u] = true;
for(int i = head[u];i;i=G[i].next){
if( dis[v] > dis[u] + G[i].dis){
dis[v] = dis[u] + G[i].dis;
if(inq[v]) return true;
if(dfs(v)) return true;
}
}inq[u] = false;
return false;
}
#undef v
int n,m;
inline bool check(double mid){
for(int i=1;i<=n+2;++i) dis[i] = inq[i] = 0;
for(int i=1;i<=n+2;++i) if(dfs(i)) return true;
return false;
}
int main(){
read(n);read(m);
for(int i=1;i<=m;++i){
static int u,v,a,b,c,d;
read(u);read(v);read(a);
read(b);read(c);read(d);
add(u,v,b+d);
if(c > 0) add(v,u,a-d);
}
double l = .0,r = 1e9;
while(r-l > eps){
double mid = (l+r)/2;
for(int i=1;i<=cnt;++i) G[i].dis += mid;
if(check(mid)) l = mid;
else r = mid;
for(int i=1;i<=cnt;++i) G[i].dis -= mid;
}
printf("%.2lf\n",l);
getchar();getchar();
return 0;
}