感觉建新图有问题,但是调不出来
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int val[N];
struct node{
int to,next;
}tr[2 * N];
int h[N],k = 0;
int n,m;
int low[N],dfn[N],num = 0,root;
bool cut[N];
int s[N],top = 0;
vector<int> dcc[N];
int cnt = 0;
int sum[N],id[N];
void out(){
cout <<"SD"<<" ";
for(int i = 1;i <= 2;i++) cout << sum[i]<<" ";
cout << endl;
}
void add(int from,int to){
tr[++k].to = to;
tr[k].next = h[from];
h[from] = k;
}
void tarjan(int x){
dfn[x] = low[x] = ++ num;
s[++top] = x;
if(x == root && h[x] == 0) {
dcc[++cnt].push_back(x);
sum[cnt] += val[x];
return ;
}
int flag = 0;
for(int i = h[x];i ; i = tr[i].next){
int y = tr[i].to;
if(!dfn[y]){
tarjan(y);
low[x] = min(low[x],low[y]);
if(x != root || flag > 1) cut[x] = 1;
int z;cnt++;
do{
z = s[top--];
dcc[cnt].push_back(z);
sum[cnt] += val[z] ;
}while(z != y);
dcc[cnt].push_back(x);
sum[x] += val[x];
}
else low[x] = min(low[x],dfn[y]);
}
}
queue<int> q;
int in[N];
int re[N];
int dp[N];
void topu(){
for( int i = 1;i <= num;i++) if(in[i] == 0) q.push(i);
while(!q.empty()){
int u = q.front();
q.pop();
re[++root] = u;
for(int i = h[u]; i ; i = tr[i].next){
int y = tr[i].to;
in[y]--;
if(in[y] == 0) q.push(y);
}
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> val[i];
for(int i = 1;i <= m; i ++){
int a,b;
cin >> a >> b;
add(a,b);
add(b,a);
}
for(int i = 1;i <= n; i ++){
if(!dfn[i]) root = i,tarjan(i);
}
num = cnt;
memset(tr,0,sizeof(tr));
memset(h,0,sizeof(h));
k = 0;
for(int i = 1; i <= n;i++) if(cut[i]) id[++num] = i;
for(int i = 1;i <= cnt;i++){
for(int j = 0;j < dcc[i].size(); j ++){
int x = dcc[i][j];
if(cut[x]) {
in[i]++;
add(i,id[x]);
add(id[x],i);
}
}
}
root = 0; //新图
cout << endl;
topu();
int ans = 0;
// for(int i = 1; i<= root;i++) cout <<re[i]<<" ";
for(int i = 1;i <= root;i++){
int x = re[i];
dp[x] = sum[x];
for(int j = h[x];j ; j = tr[j].next){
int y = tr[j].to;
cout << y;
dp[x] = max(dp[x],dp[y] +sum[x]);
}
ans = max(ans,dp[x]);
}
cout << ans;
return 0;
}