自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 21:38:19，当前版本为作者最后更新于2019-01-18 00:10:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

我觉得这是一道好题，因为它考到了许多知识，将很多知识综合了起来

思路

拿到这道题之后，我们应该将这个问题拆成两个问题

第一，求n到每个出入口的时间和与安全系数和比值最小的路径

第二，求出探索所有空腔的最小代价

做法

第一个问题

假设我们去的是点$x$,那么我们就是要找到一条从$n$到$x$的路径，使得$\sum (Ti *xi)/\sum (Si*xi )$最小，

($xi$表示第i条边在不在该路径上，若在为1，不在即为0)

我们考虑二分答案，假设我们当前二分的值为$ans$,

那如果这个答案满足条件，就要满足 $\sum (Ti *xi)/\sum (Si *xi)<=ans$，

移项可得$\sum (Ti*xi) -\sum (Si*xi)*ans<=0$，

即为$\sum((Ti-ans*Si)*xi)<=0$

那我们只要使每条边权改为$Ti-Si*xi$,然后看$n$到$x$的路径是否$<=0$即可

这就是一个简单的01分数规划，我相信看这道题的人应该都看得懂qwq

但是要求多个点到$n$的最小路径，所以考虑整体二分

但貌似听说不整体二分也过得去，如果你不会的话就一个一个二分吧233

最短路用什么方法呢？Spfa?Dijkstra?Floyed?

no no no!!!

首先，这道题有负边，所以$Dijkstra$首先淘汰，$SPFA?$,但是这道题$m$又有足足$1e5$,跑$SPFA$巨慢啊，$Floyed$对于$n<=700$来说根本不可能

那咋办啊？？

等等，我们是不是漏了什么？

没有环啊！！！

那就简单了，跑个拓扑序就完事了啊（我也不知道我前面扯那么多干嘛）

第二个问题

现在我们得到了$n$到所有出入口的最小路径，那如何求探索所有空腔的最小代价呢？

首先，我觉得题目都已经在疯狂暗示告诉我们这是个一个二分图了

-----每个空腔有且只有两个出入口，并且这两个出入口不会在同一排。为了方便起见，两排出入口分别编号为$1,3,5…$和$2,4,6…$并且最大的编号为$n1$。

两排，每个出口一排一个，这不是二分图是什么？？

其实这个网络流模型也并不难建立，

从源点往每个奇数点建边，流量为从$n$到该点的最小路径

对于每个空腔的两个出入口$u,v$,假设$u$是奇数,则从u向v建一条流量为inf的边

从每个偶数点往汇点建边，流量为从$n$到改点的最小路径

问题是为什么那么建图呢？

其实我们在这里利用的是最小割，因为对于每一个空腔的出入口$u,v$，我们必须选择一个，让$u$往$v$建inf边的意义就是我们为了让$u$和$v$分开，我们就必须在$u$和 $v$和之间选一条边割掉，割掉的代价即为从$n$到改点的最小路径，

然后由最大流最小割定理，跑最小割即可

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define inf 0x7fffffff/2
#define eps 1e-3
#define N 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
struct Edge
{
	int next,to;
	double s,t;
}E[N<<1];
int Head[N],ecnt;
int n,U[N],V[N],m,n1,m1;
int pre[N],minn[N];
double dist[N],D[N];
int depth[N],Index[N];
struct edge
{
	int next,to;
	double fl;
}e[N*10];
int head[N],cnt=1;
int q[N],ql[N],qr[N];
queue<int>qu;
int vis[N];
int pos[N],nowpos;
int ss,tt,maxflow;
int Stack[N],top;
inline void Add_edge(int from,int to,double s,double t)
{
	E[++ecnt].to=to;E[ecnt].next=Head[from];E[ecnt].s=s;E[ecnt].t=t;Head[from]=ecnt;Index[to]++;
}//对原图进行建边
inline void Topu(double x)
{
	for(register int i=1;i<n;i++)dist[i]=inf;dist[n]=0;
	for(register int i=1;i<=n;i++)
	{
		int now=pos[i];
		for(register int j=Head[now];j;j=E[j].next)
		{
			dist[E[j].to]=min(dist[E[j].to],dist[now]+E[j].t-E[j].s*x);
		}
	}
}//求最短路
void Q(double L,double R,int l,int r)
{
	if(l>r)return ;
	if(fabs(R-L)<=eps){for(register int i=l;i<=r;i++)D[q[i]]=L;return ;}
	double mid=(L+R)/2;
	Topu(mid);
	int nowl=0,nowr=0;
	for(register int i=l;i<=r;i++)if(dist[q[i]]<=0.0){ql[++nowl]=q[i];}else qr[++nowr]=q[i];
	for(register int i=l;i<=l+nowl-1;i++)q[i]=ql[i-l+1];
	for(register int i=l+nowl;i<=r;i++)q[i]=qr[i-nowl-l+1];
	Q(L,mid,l,l+nowl-1);Q(mid+eps,R,l+nowl,r);
}//整体二分
inline void add_edge(int from,int to,double fl){e[++cnt].to=to;e[cnt].next=head[from];e[cnt].fl=fl;head[from]=cnt;}
  //对网络流建边
inline int bfs()
{
	memset(depth,0,sizeof(depth));while(!qu.empty())qu.pop();
	qu.push(ss);depth[ss]=1;
	while(!qu.empty())
	{
		int x=qu.front();qu.pop();
		for(register int i=head[x];i;i=e[i].next)
		{
			if(fabs(e[i].fl-0)>=eps&&!depth[e[i].to])depth[e[i].to]=depth[x]+1,qu.push(e[i].to);
		}
	}
	return depth[tt];
}
double dfs(int now,double flow)
{
	if(now==tt)return flow;
	double ret=0;
	for(register int i=head[now];i;i=e[i].next)
	{
		if(fabs(ret-flow)<=eps)return flow;
		if(fabs(e[i].fl-0)>=eps&&depth[e[i].to]==depth[now]+1)
		{
			double fl=dfs(e[i].to,min(e[i].fl,flow-ret));
			if(fabs(fl-0)>=eps)
			{
				ret+=fl;
				e[i].fl-=fl;
				e[i^1].fl+=fl;
			}
		}
	}
	if(fabs(ret-0)<=eps)depth[now]=0;
	return ret;
}
inline double Dinic()
{
	double sum=0,x=0;
	while(bfs()){x=1;while(fabs(x-0)>=eps){x=dfs(ss,inf);sum+=x;}}
	return sum;
}//最大流，即为最小割
inline void Prepare()
{
	nowpos=0;top=0;
	for(register int i=1;i<=n;i++)if(!Index[i])Stack[++top]=i;
	while(top)
	{
		int x=Stack[top--];pos[++nowpos]=x;
		for(register int i=Head[x];i;i=E[i].next)
		{
			Index[E[i].to]--;if(!Index[E[i].to])Stack[++top]=E[i].to;
		}
	}
}//求拓扑排序
int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)q[i]=i;
	for(register int i=1;i<=m;i++)
	{
		int from,to;double s,t;
		scanf("%d%d%lf%lf",&from,&to,&t,&s);
		Add_edge(from,to,s,t);
	}
	Prepare();
	Q(0,inf,1,n-1);D[n]=0;
	m1=read(),n1=read();
	for(register int i=1;i<=m1;i++)U[i]=read(),V[i]=read();
	tt=n1+m1+1;
	for(register int i=1;i<=n1;i++)
	{
		if(i&1)add_edge(ss,i,D[i]),add_edge(i,ss,0);
		else add_edge(i,tt,D[i]),add_edge(tt,i,0);
	}
	for(register int i=1;i<=m1;i++)
	{
		if(V[i]&1)swap(U[i],V[i]);
		add_edge(U[i],V[i],inf),add_edge(V[i],U[i],0);
	}
	double ans=Dinic();
	if(ans>1e8){printf("-1\n");}
	else printf("%.1lf\n",ans);
	return 0;
}

如果认为我这篇题解对你有帮助的可以给我点一下赞qwq。如果有任何疑问，或者认为我的题解有什么问题的话，请务必私信我，感激不尽！我会努力把我的题解写得最好的!