[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\le n,q\le 2\times 10^5$
· $0\le m\le 5\times 10^5$
· $x_i?=y_i,1\le x_i,y_i\le n$
· 可能存在相异两个正整数 $i,j$ 满足 $(x_i,y_i)=(x_j,y_j)$
· $1\le h_i\le 10^9$

题解

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

设$min{b}_x$,$max{b}_x$为从$1$到$x$的路径上的最小/最大边，$min{q}_x$,$max{q}_x$为强连通内部的最小/最大边。

然后是一堆问题:

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

方案：维护一个$ta{g}_x$数组，一开始只有$ta{g}_{be{l}_1}$为ture，拓扑排序时往后传递$tag$，那么只有$tag$为ture的才计入答案即可。

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

方案：注意到参与答案计算的只有两条边，我们只需要规定一条边为当前边，那么前面的边我们只需要记录最大边和最小边即可。同时我们维护$an{s}_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]]);}
}