题解 P3288 【[SCOI2014]方伯伯运椰子】

· · 题解

题解

题目要求 总交通量不减少
若 总交通量 增加的话，一定不优
所以 总交通量 守恒
也就是 我们不生产流量 ，我们只做流量的搬运工

那么我们可以
将 压缩 看成 退流
将 扩容 看成 增广
那么 X-Y \Rightarrow \Delta总费用 \Rightarrow 压缩导致的费用-扩容导致的费用
压缩 \Rightarrow (v,u,c)(c!=0) 边权\ a-d
增广 \Rightarrow (u,v,inf)\ \ \ \ \ \ \ \ \ 边权\ b+d
这样建图后，会出现一些环，每一个环，都是一个流量搬运的途径

令 max\{\ (X-Y)/k\ \}=ans 则对于图中任意一个环，有 ans>=(X-Y)/k 可推知 ans \times k-(X-Y)>=0
我们可以二分一个mid
当 mid>=ans 时，mid \times k-(X-Y)>=0
当 mid<\ \ \ ans 时，mid \times k-(X-Y)<\ \ \ 0
并将费用 (a-d\ or\ b+d) 存成边权，将\ k\ 看成是环上的点数 (环上的点数=环上的边数= k)
也就是找到一个点就 +mid，相当于是将边权看成了 (边权+mid)
那么，当 mid \times k-(X-Y)<0\Rightarrow \sum e[i]<0(e[i]为边权) 时，这个环为一个负环
于是我们二分的判断条件就可以换成图中是否有负环
即
当\ mid>=ans\ 时，mid \times k-(X-Y)>=0\ 无负环
当\ mid<\ \ \ ans\ 时，mid \times k-(X-Y)< 0\ \ \ \ 有负环
然后spfa判负环即可

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define eps 1e-3
#define inf 1e9
#define N 5005

int n,m;
inline int read() {
    int tmp=0,w=1;
    char ch=0;
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) tmp=(tmp<<1)+(tmp<<3)+ch-'0',ch=getchar();
    return tmp*w;
}

struct node {
    int v,f,nex;
}e[N<<1];
int tot,h[N];
void add(int u,int v,int f) {
    e[++tot].v=v,e[tot].f=f,e[tot].nex=h[u],h[u]=tot;
}

bool vis[N];
double dis[N];
bool spfa(int x,double mid) {
    vis[x]=1;
    int xx;
    for(int i=h[x];i;i=e[i].nex) {
        xx=e[i].v;
        if(dis[xx]>dis[x]+e[i].f+mid) {
            dis[xx]=dis[x]+e[i].f+mid;
            if(vis[xx]) return 1;
            if(spfa(xx,mid)) return 1;
        }
    }
    vis[x]=0;
    return 0;
}
bool pd(double mid) {
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    for(int i=1;i<=n;++i) if(spfa(i,mid)) return 1;
    return 0;
}
void Bsearch() {
    double l=0,r=inf,mid;
    while(r-l>=eps) {
        mid=(l+r)/2;
        if(pd(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf",l);
}

int main()
{
    n=read()+2,m=read();
    int u,v,a,b,c,d;
    for(int i=1;i<=m;++i) {
        u=read(),v=read(),a=read(),b=read(),c=read(),d=read();
        if(c!=0) add(v,u,a-d);
        add(u,v,b+d);
    }
    Bsearch();
    return 0;
}