编译有问题啊，思路很乱
by _Cacipierio_ @ 2023-08-06 10:21:48
再次建图过程中可能有重边
by _Cacipierio_ @ 2023-08-06 10:30:13
@[zhang666yz](/user/536238)
感谢，让我来调一调
by so_find_skind @ 2023-08-06 20:44:05
@[zhang666yz](/user/536238)
调过了，还是有问题
```
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],idx[100005],cnt,colnum,col[100005],minx[100005],maxx[100005];
vector<int>g[100005];
vector<int>rg[100005];
vector<int>dg[100005];
bool vis[100005];
map<int,int>d[100005];
void dfs(int x){
vis[x]=true;//标记
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(!vis[v])
dfs(v);//深搜
}
idx[++cnt]=x;//标点
}
void rdfs(int x,int c){//染色
vis[x]=true;//标记
col[x]=c;//将x点染色为c
for(int i=0;i<rg[x].size();i++){
int v=g[x][i];
if(!vis[v])
rdfs(v,c);
}
}
int ddfs(int x,int mix,int mxx){//深搜遍历求解
if(x==col[idx[n]])//到重点了
return mxx-mix;
int ans=0;
for(int i=0;i<dg[x].size();i++){//取最大
int v=dg[x][i];
ans=max(ans,ddfs(v,min(mix,minx[v]),max(mxx,maxx[v])));
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1,u,v,op;i<=m;i++){//存图
cin>>u>>v>>op;
if(op==1){
g[u].push_back(v);
g[v].push_back(u);
}else{
g[u].push_back(v);
g[v].push_back(u);
rg[u].push_back(v);
rg[v].push_back(u);
}
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);//若未标记过，则标点
}
}
memset(vis,false,sizeof(vis));
for(int i=1;i<=cnt;i++){
if(!vis[idx[i]]){
rdfs(idx[i],++colnum);//若未标记过，则给此点染色
}
}
for(int i=1;i<=n;i++){//存缩点后的图
for(int j=0;j<g[i].size();j++){
int v=g[i][j];
if(col[idx[i]]!=col[idx[v]]){
if(!d[col[idx[i]]][col[idx[v]]]){
dg[col[idx[i]]].push_back(col[idx[v]]);
d[col[idx[i]]][col[idx[v]]]=1;
}
}
}
}
memset(minx,0x3f,sizeof(minx));
for(int i=1;i<=n;i++){//取缩的每个点的水晶球价格的最大最小
minx[col[idx[i]]]=min(minx[col[idx[i]]],a[i]);
maxx[col[idx[i]]]=max(maxx[col[idx[i]]],a[i]);
}
cout<<ddfs(col[idx[1]],minx[col[idx[1]]],maxx[col[idx[1]]]);
return 0;
}
```
by so_find_skind @ 2023-08-06 20:48:33
直接Kusarajv缩点是有一些问题的，比如一条双向边（u,v），｛u,v｝其实已经组成了强连通分量，而题目中是可以重复走的，所以可以优化一下（这里用Tarjan更方便）。我也不知道是不是这个问题，你可以再调一下 @[zhezhikongdanruxue](/user/756179)
by _Cacipierio_ @ 2023-08-06 20:59:40