网站上添加百度地图导航,包头网络推广公司,常平做网站,深网网络网站正题
题目链接:https://www.cometoj.com/contest/73/problem/E?problem_id4124 题目大意
给出nnn个点mmm条边的一张有向图#xff0c;边有边权#xff0c;qqq次询问从点111走到点xxx的所有路径#xff08;可以重复经过任何点包括点xxx#xff09;中极差最大是多少。 1≤…正题
题目链接:https://www.cometoj.com/contest/73/problem/E?problem_id4124 题目大意
给出nnn个点mmm条边的一张有向图边有边权qqq次询问从点111走到点xxx的所有路径可以重复经过任何点包括点xxx中极差最大是多少。
1≤n≤2×105,1≤m≤5×1051\leq n\leq 2\times 10^5,1\leq m\leq 5\times 10^51≤n≤2×105,1≤m≤5×105 解题思路
首先肯定要tarjantarjantarjan缩点然后考虑怎么统计极差。
考虑到极差其实到某个位置的时候就已经不会再改变了而且这个到这个位置的路径一定是作为最小值或者最大值的。
所以我们可以维护一个路径上的最大值/最小值和最大极差然后每次考虑新的转移会不会更新极差就可以了。
时间复杂度O(nm)O(nm)O(nm)
CometOJ评测机炸了代码没测就当过了吧… code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includequeue
#includestack
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N2e510;
int n,m,t,cnt,dfn[N],low[N],col[N],in[N];
int mi[N],mx[N],Mi[N],Mx[N],ans[N];
stackint s;queueint q;bool ins[N];
vectorpairint,int G[N],T[N];
void tarjan(int x){dfn[x]low[x]cnt;ins[x]1;s.push(x);for(int i0;iG[x].size();i){int yG[x][i].first;if(!dfn[y]){tarjan(y);low[x]min(low[x],low[y]);}else if(ins[y])low[x]min(low[x],dfn[y]);}if(dfn[x]low[x]){while(s.top()!x){col[s.top()]x;ins[s.top()]0;s.pop();}col[x]x;ins[x]0;s.pop();}return;
}
void Topsort(){for(int i1;in;i)if(!in[i])q.push(i);while(!q.empty()){int xq.front();q.pop();Mx[x]max(Mx[x],mx[x]);Mi[x]min(Mi[x],mi[x]);ans[x]max(ans[x],mx[x]-Mi[x]);ans[x]max(ans[x],Mx[x]-mi[x]);for(int i0;iT[x].size();i){int yT[x][i].first,wT[x][i].second;in[y]--;Mx[y]max(Mx[y],max(Mx[x],w));Mi[y]min(Mi[y],min(Mi[x],w));ans[y]max(ans[y],ans[x]);ans[y]max(ans[y],w-Mi[x]);ans[y]max(ans[y],Mx[x]-w);if(!in[y])q.push(y);}}return;
}
int main()
{scanf(%d%d%d,n,m,t);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);G[x].push_back(mp(y,w));}tarjan(1);memset(mi,0x3f,sizeof(mi));memset(Mi,0x3f,sizeof(Mi));for(int x1;xn;x){for(int i0;iG[x].size();i){int yG[x][i].first,wG[x][i].second;ycol[y];if(col[x]y)mx[y]max(mx[y],w),mi[y]min(mi[y],w);else T[col[x]].push_back(mp(y,w)),in[y];}}Topsort();while(t--){int x;scanf(%d,x);if(x1||!col[x])puts(-1);else printf(%d\n,ans[col[x]]);}return 0;
}
