自动搬运

查看原文

来自洛谷，原作者为

	bsTiat 未来始终掌握在自己手中，从中滑落的，我们称之为过去。

搬运于2025-08-24 22:33:29，当前版本为作者最后更新于2021-10-11 21:58:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

我们用 $ans_i$ 表示从城市 $i$ 出发可以一直走下去的最小花费，所有 $ans_i$ 初始赋值为 $inf$，方便更新最小值，最后输出的时候判断一下如果为 $inf$ 就输出 $-1$。

首先，对于出度为 $0$ 的城市，我们可以直接将其删去，因为无论有多少钱都不可能一直走下去，其答案即为 $-1$。

那么，剩下的点都有出边，所以剩下的点一定有答案。

最初的思路——错误的想法

依次考虑从城市 $i$ 开始，但是我们可以发现，城市 $i$ 的答案不能一开始就求出，如果从城市 $i$ 开始，那么我们每经过的一个城市都可能对城市 $i$ 的答案造成更新，进而要回溯到之前的每一个城市更新，时间复杂度太大会超时。

正确的想法

换一种思路，当有多少钱时，从城市 $i$ 出发一定能一直走下去呢？当我们的钱数为当前最大的 $r_i$ 时，可以一直走下去，因为当前的 $r_i$ 是全场最大的，且 $p_i$ 均不小于 $0$，所以我们就可以一直走，不可能存在不能通行的道路。

可以采用一种类似于 拓扑排序 的算法，结合 贪心 思想。

1. 把所有所有边按 $r_i$ 排个序，每次取出 $r$ 最大的那条边 $edge_i$，设这条边起点为 $u$，更新 $u$ 的答案 $ans_u = \min(ans_u,r_i)$。

2. 如果这个点还有其它出边，那么我们就先记下这个答案，并删掉这条边。

3. 如果这个点没有其它出边了，那么这个点答案就是确定的，将这个点入队，删掉这个点，这时可能会出现新的没有出度的点，它们的答案也确定了。

4. 每一轮入队的点，在处理下一条边之前先处理，取出这个点的每一条进入的边 $edge_i$，设其起点为 $u$，终点为 $v$，更新 $u$ 的答案 $ans_u=\min(ans_u,\max(r_i,ans_v-p_i))$。 删去这条边，注意，在这过程中可能还会出现新的没有入度的点，也要记得进队。

5. 重复如此，直到没有点。

算法实现

$vis_i$ 表示第 $i$ 条边是否被删去，$dep_i$ 表示这条边的出度。

存储

struct node{
	int a,b,r,p;
	bool operator<(const node &x)const{	//因为等下是用链式前向星存边
		return r<x.r;					//读的时候是逆序的，所以按升序排
	}									//依次遍历边的时候再反过来
}edge[N];
queue<int>q;
int ans[N],vis[N],n,m,dep[N];
int head[N],nxt[N],to[N],tot;
inline void add(int &x,int &y){		
	//链式前向星存边的编号，y不是终点,而是边的编号
	to[++tot]=y;nxt[tot]=head[x];head[x]=tot
}

读入&排序

memset(ans,0x3f,sizeof(ans));
n=read();m=read();
for(i=1;i<=m;++i){
	edge[i].a=read();edge[i].b=read();
	edge[i].r=read();edge[i].p=read();
	++dep[edge[i].a];
}
sort(edge+1,edge+1+m);
for(i=1;i<=m;++i) add(edge[i].b,i);		//存储每个点的入边的编号
for(i=1;i<=n;++i) if(!dep[i])q.push(i);	//将没有出边的点入队

每次入队的点的处理

while(!q.empty()){
	u=q.front();q.pop();	
	for(j=head[u];j;j=nxt[j]){			 //k存的是边的编号
     		k=to[j];if(vis[k])continue; //如果这条边被删了就跳过
		vis[k]=1;--dep[edge[k].a];		 //处理当前点
		if(!dep[edge[k].a])q.push(edge[k].a);
		if(ans[u]!=INF)					 //更新答案
        		ans[edge[k].a]=min(ans[edge[k].a],max(edge[k].r,ans[u]-edge[k].p));
	}
}

依次处理每条边

for(i=m;i>=1;--i){					    //与每次入队的点的处理的类似
	if(!vis[i]){
		vis[i]=1;--dep[edge[i].a];
		if(!dep[edge[i].a])q.push(edge[i].a);
		ans[edge[i].a]=min(ans[edge[i].a],edge[i].r);//更新答案
	}
}

完整代码

#include<bits/stdc++.h>
# define INF (0x3f3f3f3f)
# define reg register
# define min(x,y) (x<y?x:y)
# define max(x,y) (x>y?x:y)
# define N (200005)
using namespace std;
inline int read(){
	reg char c=getchar();reg int sum=0,f=1;
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c<='9'&&c>='0'){sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}
	return sum*f;
}
struct node{
	int a,b,r,p;
	bool operator<(const node &x)const{
		return r<x.r;
	}
}edge[N];
queue<int>q;
int ans[N],vis[N],n,m,dep[N];
int head[N],nxt[N],to[N],tot;
inline void add(int &x,int &y){
	to[++tot]=y;nxt[tot]=head[x];head[x]=tot;
}
int main(){
	reg int i,j,k,u,v;
	memset(ans,0x3f,sizeof(ans));
	n=read();m=read();
	for(i=1;i<=m;++i){
		edge[i].a=read();edge[i].b=read();
		edge[i].r=read();edge[i].p=read();
		++dep[edge[i].a];
	}
	sort(edge+1,edge+1+m);
	for(i=1;i<=m;++i) add(edge[i].b,i);
	for(i=1;i<=n;++i) if(!dep[i])q.push(i);
	for(i=m;i>=1;--i){
		while(!q.empty()){
			u=q.front();q.pop();
			for(j=head[u];j;j=nxt[j]){
				k=to[j];if(vis[k])continue;
				vis[k]=1;--dep[edge[k].a];
				if(!dep[edge[k].a])	q.push(edge[k].a);
				if(ans[u]!=INF)
					ans[edge[k].a]=min(ans[edge[k].a],max(edge[k].r,ans[u]-edge[k].p));
			}
		}
		if(!vis[i]){
			vis[i]=1;--dep[edge[i].a];
			if(!dep[edge[i].a])q.push(edge[i].a);
			ans[edge[i].a]=min(ans[edge[i].a],edge[i].r);
		}
	}
	for(i=1;i<=n;++i) printf("%d ",(ans[i]==INF?-1:ans[i]));
	return 0;
}

这是本蒟蒻第一次写题解，如有不足多多见谅，有意见或错误欢迎提出。