[Comet OJ Contest 14][tarjan缩点+拓扑排序dp]E.飞翔的小鸟_综合

这题真的很NOIP啊（~~虽然它已经死了~~）

题面

一日，小鸟想要进行旅行。
旅程图由 $n$ 个景点与 $m$ 条有向通道组成，景点和通道皆由 $1$ 开始编号。第 $i$ 条通道起点为第 $x_i$ 个景点，终点为第 $y_i$ 个景点，并且有个高度参数 $h_i$ ，表示此条通道的缺口高度，当且仅当小鸟在此高度时能够通过这条通道。

在每个景点会有休息的位置，小鸟可以在此任意调节自己的高度。

小鸟非常地喜欢刺激的旅程，他想让自己通过的通道的最大高度与最小高度的差最大。即使到达了终点，也不一定要立即结束旅行，小鸟仍可以再去其他景点后再绕回来。

有 $q$ 次询问，第 $i$ 次询问会给你一个景点编号 $t_i$ ，请输出以 $1$ 号景点为起点， $t_i$ 为终点时，小鸟旅行中走过的路线中最大高度与最小高度差的最大值，若不存在经过的通道数目大于 $0$ 的路线，输出 -1。
· $1≤n,q≤2×1051\le n,q\le 2×10^5$
· $\le m \le 5 \times 10^5$
· $xi≠yi,1≤xi,yi≤nx_i \ne y_i, 1 \le x_i,y_i \le n$
· 可能存在相异两个正整数 $i, j$ 满足 $x_i,y_i) = (x_j, y_j)$
· $\le h_i \le 10^9$
[Comet OJ Contest 14][tarjan缩点+拓扑排序dp]E.飞翔的小鸟

题解

前面是一堆套路:
首先有一个显然的结论：在一个环内，小鸟一定可以任意访问一个节点任意次。
那么我们可以直接将有向图的强连通分量缩成一个点，保留最大边和最小边即可。
然后这个图就成了一个DAG。
显然接下来我们就可以愉快的开始DP了。
首先我们需要一些定义:

设 $minb_x$ , $maxb_x$ 为从 $1$ 到 $x$ 的路径上的最小/最大边， $minq_x$ , $maxq_x$ 为强连通内部的最小/最大边。

然后是一堆问题:

做拓扑排序时， $1$ 号点所在强连通不一定度数为0，怎么限制它为起点

方案：维护一个 $tag_x$ 数组，一开始只有 $tag_{bel_1}$ 为ture，拓扑排序时往后传递 $t a g$ ，那么只有 $t a g$ 为ture的才计入答案即可。

例如样例图片（见上）所示，从 $1$ 到 $3$ 有两条路径，我们该怎么选择路径?

方案：注意到参与答案计算的只有两条边，我们只需要规定一条边为当前边，那么前面的边我们只需要记录最大边和最小边即可。同时我们维护 $ans_x$ 为 $1 ? x$ 的最大答案，在当前更新一下即可。（具体请见代码）

于是这道题就被我们 $O (n)$ 解决了，注意细节，真的很多…

实现

/*Lower_Rating*/
/*Comet 14 飞翔的小鸟*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<vector>
#include<queue>
using namespace std;#define LL long long
#define DB double
#define MAXN 500000
#define INF 2000000001
#define mem(x,p) memset(x,p,sizeof(x))LL read(){
    LL x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*F;
}int n,m,q;
int dfn[MAXN+5],low[MAXN+5],ct,Bcnt;
int stk[MAXN+5],bel[MAXN+5],to,tp;
int bmx[MAXN+5],bmn[MAXN+5],dmn[MAXN+5],dmx[MAXN+5],ans[MAXN+5];
int du[MAXN+5],tag[MAXN+5];
queue<int> Q;
struct Graph{
    int head[MAXN+5],ecnt;struct edge{
    int to,nxt,w;}e[MAXN+5];void init(){
    ecnt=0;mem(head,-1);}void add(int u,int v,int w){
    e[++ecnt]=(edge){
    v,head[u],w};head[u]=ecnt;}
}G,nG;
struct EDGE{
    int u,v,w;
}E[MAXN+5];
void tarjan(int x){
    dfn[x]=low[x]=++ct,stk[++tp]=x;for(int i=G.head[x];i!=-1;i=G.e[i].nxt){
    int v=G.e[i].to;if(!dfn[v]){
    tarjan(v);low[x]=min(low[x],low[v]);}else if(!bel[v])low[x]=min(low[x],dfn[v]);}if(dfn[x]==low[x]){
    Bcnt++;int p;do{
    p=stk[tp],bel[p]=Bcnt,tp--;}while(p!=x);}
}
int main()
{
    G.init(),nG.init();n=read(),m=read(),q=read();for(int i=1;i<=m;i++){
    int u=read(),v=read(),h=read();G.add(u,v,h);E[i]=(EDGE){
    u,v,h};}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=Bcnt;i++)bmn[i]=INF,bmx[i]=0,dmn[i]=INF,dmx[i]=0,ans[i]=0;for(int i=1;i<=m;i++)if(bel[E[i].u]==bel[E[i].v]){
    int x=bel[E[i].u];bmn[x]=min(bmn[x],E[i].w);bmx[x]=max(bmx[x],E[i].w);}else{
    nG.add(bel[E[i].u],bel[E[i].v],E[i].w);du[bel[E[i].v]]++;}tag[bel[1]]=1;for(int i=1;i<=Bcnt;i++)if(!du[i])Q.push(i);while(!Q.empty()){
    int x=Q.front();Q.pop();if(tag[x]){
    //加上自己的点权记录答案dmn[x]=min(dmn[x],bmn[x]);dmx[x]=max(dmx[x],bmx[x]);ans[x]=max(ans[x],max(bmx[x]-dmn[x],dmx[x]-bmn[x]));}for(int i=nG.head[x];i!=-1;i=nG.e[i].nxt){
    int v=nG.e[i].to,w=nG.e[i].w;du[v]--;if(tag[x]){
    dmn[v]=min(min(dmn[v],dmn[x]),w);dmx[v]=max(max(dmx[v],dmx[x]),w);ans[v]=max(max(ans[x],ans[v]),max(w-dmn[x],dmx[x]-w));tag[v]=1;}if(!du[v])Q.push(v);}}while(q--){
    int x=read();if(dmn[bel[x]]>dmx[bel[x]])printf("-1\n");else printf("%d\n",ans[bel[x]]);}
}