bzoj3597 [Scoi2014]方伯伯运椰子

【题意】

略。

【数据范围】

n<=5000，m<=3000

【思路】

求(X-Y)/k的最大值，使用分数规划，二分答案后每条边均摊代价。问题转化为判断是否存在一种修改方案使得总费用减小。

显然问题等价于判断是否存在一种只修改1的容量的方案使得总费用减小。

如果只修改1的容量，为了满足流量限制，可以发现修改的边构成了一个环，其中一部分是容量-1，另一部分是容量+1。如果把+1的边反向，则这个环是定向的。

设当前二分的答案为mid，则容量+1的花费=b[i]+mid+d[i]，容量-1的花费=a[i]+mid-d[i]。c[i]>=1的边容量可减可加，建双向边；c[i]=0的边容量只能加，建单向边。

问题转化为判断是否存在有向负环，使用dfs版spfa即可。

【时间复杂度】

O((n+m) log (Di))

#include<cstdio>
#include<cstring>
#include<algorithm>
#define eps 1e-5
#define N 5010
#define M 3010
using namespace std;
 
struct edge{int x, y, next; double z;}a[M*2];
struct bb{int x, y, a, b, c, d;}b[M];
int n, m, flag[N], l, p[N], ff;
double L, R, mid, h[N];
 
void add(int x, int y, double z){
    a[++l].x=x; a[l].y=y; a[l].z=z; a[l].next=p[x]; p[x]=l;
}
 
void dfs_spfa(int x){
    flag[x]=1;
    for(int i=p[x]; i&&!ff; i=a[i].next)
        if(h[a[i].y]>h[x]+a[i].z){
            if(flag[a[i].y])ff=1;
            else{
                h[a[i].y]=h[x]+a[i].z;
                dfs_spfa(a[i].y);
            }
        }
    flag[x]=0;
}
int check(double k){
    l=0; memset(p, 0, sizeof(p));
    for(int i=1; i<=m; i++){
        if(b[i].c)add(b[i].x, b[i].y, b[i].a+k-b[i].d);
        add(b[i].y, b[i].x, b[i].b+k+b[i].d);
    }
    memset(flag, 0, sizeof(flag));
    for(int i=1; i<=n; i++)h[i]=0; ff=0;
    for(int i=1; i<=n&&!ff; i++)dfs_spfa(i);
    return ff;
}
 
int main(){
    scanf("%d%d", &n, &m); n+=2;
    for(int i=1; i<=m; i++)scanf("%d%d%d%d%d%d", &b[i].x, &b[i].y, &b[i].a, &b[i].b, &b[i].c, &b[i].d);
    L=0; R=10000000;
    while(R-L>eps){
        mid=(L+R)/2;
        if(check(mid))L=mid; else R=mid;
    }
    printf("%.2f", L);
    return 0;
}