求小规模点的数据 /thx
by Q__A__Q @ 2023-10-12 23:31:40
```cpp
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("Ofast")
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair((a),(b))
#define int ll
const int maxn=5e5+10;
const int inf=1e12;
const int mod=1e9+7;
int n,m,k,ans,val[maxn];
vector<int> h[maxn],g[maxn],tmp[maxn];
inline int read() {
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void write(int x) {
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar('0'+x%10);
}
int dfn[maxn],low[maxn],ins[maxn],col[maxn],mx[maxn],mn[maxn];
int color,dfsnum;
stack<int> st;
inline void tarjan(int u) {
dfn[u]=low[u]=++dfsnum;
st.push(u);
ins[u]=1;
for(int v:h[u]) {
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
} else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]) {
++color;
col[u]=color;
ins[u]=0;
mx[color]=max(mx[color],val[u]);
mn[color]=min(mn[color],val[u]);
while(st.top()!=u) {
col[st.top()]=color;
ins[st.top()]=0;
mx[color]=max(mx[color],val[st.top()]);
mn[color]=min(mn[color],val[st.top()]);
st.pop();
}
st.pop();
}
}
int u[maxn],v[maxn],in[maxn];
inline void top() {
queue<int> q;
q.push(col[1]);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int v:g[u]) {
if(--in[v]==0) {
tmp[u].push_back(v);
q.push(v);
}
}
}
}
inline void dfs(int u,int minx) {
ans=max(ans,mx[u]-minx);
for(int v:tmp[u]) {
dfs(v,min(minx,mn[v]));
}
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(),m=read();
for(int i=1; i<=n; ++i) val[i]=read();
for(int i=1; i<=m; ++i) {
u[i]=read(),v[i]=read();
int w=read();
h[u[i]].push_back(v[i]);
if(w==2) h[v[i]].push_back(u[i]);
}
memset(mn,127,sizeof mn);
memset(mx,-127,sizeof mx);
for(int i=1; i<=n; ++i)
if(!dfn[i]) tarjan(i);
for(int i=1; i<=m; ++i) {
if(col[u[i]]==col[v[i]]) continue;
g[col[u[i]]].push_back(col[v[i]]);
in[col[v[i]]]++;
}
mx[0]=-inf,mn[0]=inf;
top();
dfs(col[1],mn[col[1]]);
write(ans),puts("");
return 0;
}
/*
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
*/
```
by Q__A__Q @ 2023-10-12 23:32:27
20pts求调
by Q__A__Q @ 2023-10-12 23:55:09