题解 P7831 【Travelling Merchant】
bsTiat
·
·
题解
题目分析
我们用 ans_i 表示从城市 i 出发可以一直走下去的最小花费，所有 ans_i 初始赋值为 inf ，方便更新最小值，最后输出的时候判断一下如果为 inf 就输出 -1 。
首先，对于出度为 0 的城市，我们可以直接将其删去，因为无论有多少钱都不可能一直走下去，其答案即为 -1 。
那么，剩下的点都有出边，所以剩下的点一定有答案。
最初的思路——错误的想法
依次考虑从城市 i 开始，但是我们可以发现，城市 i 的答案不能一开始就求出，如果从城市 i 开始，那么我们每经过的一个城市都可能对城市 i 的答案造成更新，进而要回溯到之前的每一个城市更新，时间复杂度太大会超时。
正确的想法
换一种思路，当有多少钱时，从城市 i 出发一定能一直走下去呢？当我们的钱数为当前最大的 r_i 时，可以一直走下去，因为当前的 r_i 是全场最大的，且 p_i 均不小于 0 ，所以我们就可以一直走，不可能存在不能通行的道路。
可以采用一种类似于 拓扑排序 的算法，结合 贪心 思想。
-
把所有所有边按 r_i 排个序，每次取出 r 最大的那条边 edge_i ，设这条边起点为 u ，更新 u 的答案 ans_u = \min(ans_u,r_i) 。
-
如果这个点还有其它出边，那么我们就先记下这个答案，并删掉这条边。
-
如果这个点没有其它出边了，那么这个点答案就是确定的，将这个点入队，删掉这个点，这时可能会出现新的没有出度的点，它们的答案也确定了。
-
每一轮入队的点，在处理下一条边之前先处理，取出这个点的每一条进入的边 edge_i ，设其起点为 u ，终点为 v ，更新 u 的答案 ans_u=\min(ans_u,\max(r_i,ans_v-p_i)) 。 删去这条边，注意，在这过程中可能还会出现新的没有入度的点，也要记得进队。
-
重复如此，直到没有点。
算法实现
#### 存储
```cpp
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
}
```
#### 读入&排序
```cpp
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); //将没有出边的点入队
```
#### 每次入队的点的处理
```cpp
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));
}
}
```
#### 依次处理每条边
```cpp
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);//更新答案
}
}
```
## 完整代码
```cpp
#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;
}
```
这是本蒟蒻第一次写题解，如有不足多多见谅，有意见或错误欢迎提出。