求助 Tarjan
查看原帖
求助 Tarjan
420102
phmaprostrate楼主2021/9/24 09:18

感觉建新图有问题,但是调不出来

#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;
}
2021/9/24 09:18
加载中...