3597: [Scoi2014]方伯伯运椰子
Time Limit: 30 Sec Memory Limit: 64 MB
Submit: 594 Solved: 360
[Submit][Status][Discuss]
Description
Input
第一行包含二个整数N，M
接下来M行代表M条边，表示这个交通网络
每行六个整数，表示Ui,Vi,Ai,Bi,Ci,Di
接下来一行包含一条边，表示连接起点的边
Output
一个浮点数，保留二位小数。表示答案，数据保证答案大于0
Sample Input
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 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
Sample Output
103.00
HINT
1<=N<=5000
0<=M<=3000
1<=Ui,Vi<=N+2
0<=Ai,Bi<=500
0<=Ci<=10000
0<=Di<=1000
很容易就可以想到01分数规划，然后思考怎么判断是否有可行解
一次完整的修改应该是找两条路径，一条路径容量扩大1，流量扩大1，另一条流量-1，容量缩小1
如果第一条路径上的边为e1，第二条路径上的边为e2，代价就是 $\sum{a_{e1}}+\sum{d_{e1}}-\sum{d_{e2}}+\sum{b_{e2}}$
可以发现这两条路径除掉前面的公共路径之后可以形成一个无向环，并且一条边的扩容、缩容付出的代价是独立的
得到一个思路：建立双向边，正向边权是扩容代价，如果容量上限不为0，反向边权是缩容代价，否则不建反向边
由于题目的答案分式和变化的容量无直接关系，所以容量变化1和变化x是没有区别的，直接检查容量变化1是否可行
01规划判断的时候，把每个环的权值定义为 $边数*mid+\sum边权$
把每条边权值加上mid后找负环，如果存在负环就有可行解，否则没有
#include<bits/stdc++.h>
#define N 5010
using namespace std;
const double eps=1e-;
int n,m,tot,fg,hd[N],vis[N];double d[N];
struct edge{int v,w,next;}e[N<<];
void adde(int u,int v,int w){
e[++tot].v=v;
e[tot].next=hd[u];
e[tot].w=w;
hd[u]=tot;
}
void dfs(int u,double x){
vis[u]=;
if(fg)return;
for(int i=hd[u];i;i=e[i].next){
int v=e[i].v;
if(d[v]>d[u]+x+e[i].w){
d[v]=d[u]+x+e[i].w;
if(vis[v]){fg=;return;}
dfs(v,x);
}
}
vis[u]=;
}
bool check(double x){
fg=;memset(d,,sizeof(d));
memset(vis,,sizeof(vis));
for(int i=;i<=n&&!fg;i++)dfs(i,x);
return fg;
}
int main(){
scanf("%d%d",&n,&m);
n+=;int u,v,a,b,c,d;
for(int i=;i<=m;i++){
scanf("%d%d%d%d%d%d",&u,&v,&a,&b,&c,&d);
adde(u,v,b+d);if(c)adde(v,u,a-d);
}
double l=,r=1e6,mid,ans;
while(l+eps<=r){
mid=(l+r)/;
if(check(mid))l=ans=mid;
else r=mid;
}
printf("%.2lf\n",ans);
return ;
}