自动搬运

查看原文

来自洛谷，原作者为

	硫代硫酸钠 **

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

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

以下是正文

首先不要被标题迷惑哦,这个题跟费用流关系不大.

然后就是重边,个人认为重边不应去除,理由如下:

显然根据本题的模型,在答案的最大流方案中流量最高的边收费p即可.

这样就导致简单合并边可能不对. 虽然这种做法能骗到80

正解:

在答案的最大流方案中流量最高的边收费p,要求答案最大流方案流量最多的边实际流量最小.考虑二分流量上界,对于上界判断是否能形成最大流.

本蒟蒻第一道实数二分...

#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define size 500010
#define debug(x) cerr<<#x<<"="<<x
#define gc getchar()
#define tp to[p]
#define inf 1e9+9
#define eps 1e-5
#define ll long long
#define db double
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#define drep(i,n,s) for (register int i=n;i>=s;i--)
#define il inline
using namespace std;

il ll r()
{
    char c; ll x,f=1;
    for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
    for (c=gc;isdigit(c);c=gc) x=(x<<1)+(x<<3)+c-'0';
    return f*x;
}

int head[size],to[size],nxt[size],num=1,S,T,sta[size],q[size],n,m,cur[size];
db mx,len[size],lim=1e15,lenn[size],p;

void add(int x,int y,db z)
{
    num++; to[num]=y;lenn[num]=z; nxt[num]=head[x];head[x]=num;
}

void create(int x,int y,db z) { add(x,y,z); add(y,x,0); }

bool bfs()
{
	int f=0,r=0;
	memset(sta,-1,sizeof(sta));
	q[++r]=S,sta[S]=0;
	while (f<r)
	{
		int x=q[++f]; 
		for (int p=head[x];p;p=nxt[p])
			if (len[p]>0&&sta[tp]==-1) sta[tp]=sta[x]+1,q[++r]=tp;		
	}
	if (~sta[T]) return 1; return 0; 
}

db dfs(int x,db flow)
{
	if (x==T) return flow;
	db now=0,used=0;
	for (int &p=cur[x];p;p=nxt[p])
		if (len[p]>0&&sta[tp]==sta[x]+1)
		{
			now=dfs(tp,min(len[p],flow-used)); used+=now;
			len[p]-=now; len[p^1]+=now; if (used==flow) break;
		}
	return used; 
}

void init()
{
	rep(i,1,num) len[i]=min(lenn[i],lim); 
}

db dinic()
{
	db ans=0;
	while (bfs())
	{
		rep(i,1,n) cur[i]=head[i];
		ans+=dfs(S,1e9+7); 
	}
	return ans;
}

int main()
{
    n=r(),m=r(); S=1,T=n; cin>>p;
    rep(i,1,m) 
    {
    	int x,y; db z;
       	scanf("%d%d%lf",&x,&y,&z); create(x,y,z);
    }
    init(); 
    db mf=dinic();printf("%.4lf\n",mf);
	db lb=0,rb=1e9,ans=0;
	while (rb-lb>0.00001) 
	{
		db mid=(lb+rb)/2;
		lim=mid; init();
		db nowflow=dinic();
		if (fabs(nowflow-mf)<0.00001) rb=mid,ans=mid;
		else lb=mid; 
	}
    lim=ans; init(); int t=dinic();  db mx=0;
    for (int i=1;i<=num;i+=2)  mx=max(mx,len[i]); printf("%.5lf",mx*p); 
    return 0;
}