@[Maxmilite](/user/274993)
@[E_Space](/user/7528)
@[离散小波变换°](/user/68344)
by LKX_Wata @ 2023-01-07 17:50:51
@[Maxmilite](/user/274993) @[E_Space](/user/7528) @[离散小波变换°](/user/68344)
by 心灵震荡 @ 2023-01-07 17:51:05
thx！
by LKX_Wata @ 2023-01-07 17:51:47
然后
```cpp
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 10, M = 1e6 + 10;
int dfn[N], col[N], low[N], stk[N], top, tim, ccn, n, m, q, a[N], minv[N], maxv[N], deg[2][N], I1, In;
bool ins[N], vis[2][N], ok[2][N];
vector <int> G[N];
set <int> gg[2][N];
struct Edge {
int u, v;
} E[M];
void Tarjan(int x) {
dfn[x] = low[x] = ++tim;
stk[++top] = x, ins[x] = 1;
for(const auto y : G[x]) {
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]) {
int y;
ccn++;
do {
y = stk[top--];
ins[y] = 0, col[y] = ccn;
} while(x != y);
}
}
bool Dfs1(int u) {
if(u == In) return 1;
if(vis[0][u]) return ok[0][u];
vis[0][u] = 1;
for(const auto& v : gg[0][u]) {
bool flg = Dfs1(v);
ok[0][u] |= flg;
if(flg)
maxv[u] = max(maxv[u], maxv[v]);
}
if(!ok[0][u]) maxv[u] = 0;
return ok[0][u];
}
bool Dfs2(int u) {
if(u == I1) return 1;
if(vis[1][u]) return ok[1][u];
vis[1][u] = 1;
for(const auto& v : gg[1][u]) {
bool flg = Dfs2(v);
ok[1][u] |= flg;
if(flg)
minv[u] = min(minv[u], minv[v]);
}
if(!ok[1][u]) minv[u] = 0x3f3f3f3f;
return ok[1][u];
}
int main() {
memset(minv, 0x3f, sizeof(minv));
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=m; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back(v);
E[++q] = {u, v};
if(--w) {
G[v].push_back(u);
E[++q] = {v, u};
}
}
for(int i=1; i<=n; i++) {
if(!dfn[i]) Tarjan(i);
}
for(int i=1; i<=n; i++) {
minv[col[i]] = min(minv[col[i]], a[i]);
maxv[col[i]] = max(maxv[col[i]], a[i]);
}
I1 = col[1];
In = col[n];
for(int i=1; i<=q; i++) {
gg[0][col[E[i].u]].insert(col[E[i].v]);
gg[1][col[E[i].v]].insert(col[E[i].u]);
++deg[0][col[E[i].v]];
++deg[1][col[E[i].u]];
}
for(int i=1; i<=ccn; i++) {
if(!deg[0][i]) Dfs1(i); //i -> n max
if(!deg[1][i]) Dfs2(i); //1 -> i min
}
int res = 0;
for(int i=1; i<=ccn; i++) {
if(ok[0][i] && ok[1][i])
res = max(res, maxv[i] - minv[i]);
}
cout << res << endl;
}
```
样例过不了但也AC了（可以通过上面Hack）
by LKX_Wata @ 2023-01-07 17:54:24
@[lightning_wave](/user/380730) 数据已经添加，感谢您的贡献。
by Maxmilite @ 2023-01-07 20:40:54
这次不可能再锅了^=^
by LKX_Wata @ 2023-01-07 20:55:49