自动搬运

查看原文

来自洛谷，原作者为

	雨季 **

搬运于2025-08-24 21:47:21，当前版本为作者最后更新于2018-03-03 11:31:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

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

那么我们可以
将 压缩 看成 退流
将 扩容 看成 增广
那么 $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;
}