Tarjan缩强连通分量+拓扑序dp
对缩点后的连通分量保存各分量内最大和最小值
测试点1 Accepted / 61ms / 11580kB
测试点2 Accepted / 65ms / 11580kB
测试点3 Accepted / 69ms / 11580kB
测试点4 Accepted / 183ms / 12768kB
测试点5 Accepted / 242ms / 13032kB
测试点6 Accepted / 71ms / 11580kB
测试点7 Accepted / 78ms / 11580kB
测试点8 Accepted / 121ms / 12088kB
测试点9 Accepted / 218ms / 13300kB
测试点10 Accepted / 196ms / 13284kB
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
#define MAXN 100010
#define MAXM 1000010
#define INF 0x3f3f3f3f
typedef long long LL;
LL dp[MAXN],f[MAXN],a[MAXN],bin[MAXN],sout[MAXN];
int n,m,bcc[MAXN],dfsno,bccno,s[MAXN],stop,dfn[MAXN],low[MAXN],ind[MAXN];
bool ins[MAXN];
vector<vector<int> > adj(MAXN),map(MAXN);
void tarjan(int u) {
dfn[u]=low[u]=++dfsno;
ins[u]=true;
s[stop++]=u;
for(int i=0;i<adj[u].size();i++) {
int v=adj[u][i];
if(dfn[v]==0) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) {
bccno++;
while(1) {
int p=s[--stop];
ins[p]=false;
bcc[p]=bccno;
bin[bccno]=min(bin[bccno],a[p]);
sout[bccno]=max(sout[bccno],a[p]);
if(p==u) break;
}
}
}
int main() {
fill(bin,bin+MAXN,INF);
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=0;i<m;i++) {
scanf("%d%d%d",&x,&y,&z);
adj[x].push_back(y);
if(z==2) adj[y].push_back(x);
}
tarjan(1);
for(int u=1;u<=n;u++) {
for(int i=0;i<adj[u].size();i++) {
int v=adj[u][i];
if(bcc[u]!=bcc[v]) {
ind[bcc[v]]++;
map[bcc[u]].push_back(bcc[v]);
}
}
}
queue<int> q;
q.push(bcc[1]);
dp[bcc[1]]=0ll;
f[bcc[1]]=bin[bcc[1]];
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0;i<map[u].size();i++) {
int v=map[u][i];
f[v]=min(f[u],bin[v]);
dp[v]=max(dp[u],sout[v]-f[v]);
ind[v]--;
if(ind[v]==0) q.push(v);
}
}
printf("%lld\n",dp[bcc[n]]);
return 0;
}