tarjan0分
查看原帖
tarjan0分
626781
nzcnnr楼主2022/4/4 13:55

tarjan0分求助 就是跑了一套塔尖,建了一个新图,dfs之后除了样例都没过

#include<stdio.h>
#include<vector>
#include<stack>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,cnt=1;
stack<int>stac;
vector<int>nmap[50005];
vector<int>map[50005];
int ans[10005],rasn,num,real;
int low[10005],dfsn[10005],frank,point[10001],value[10001];
bool vis[10005],sta[10005],clor[10001],travel[10001],color[10001],findit;
void dfs(int a){
	travel[a]=1;
	findit=0;
	for(int i=0;i<nmap[a].size();i++){
		if(travel[nmap[a][i]]==0){
			findit=1;
			num+=point[a];
			if(num>real){
				real=num;
			}
			dfs(nmap[a][i]);
			num-=point[a];
		}
	}
}
void Tarjan(int a){
	vis[a]=1;
	low[a]=dfsn[a]=cnt;
	cnt++;
	stac.push(a);
	sta[a]=1;
	for(int i=0;i<map[a].size();i++){
		int v=map[a][i];
		if(vis[v]==0){
			Tarjan(v);
			low[a]=min(low[a],low[v])	;		
		}
		else if(sta[v]==1){
			low[a]=min(low[a],low[v]);
		}

	}
			if(dfsn[a]==low[a]){
				frank++;
				while(a!=stac.top()){
					sta[stac.top()]=0;
					stac.pop();
					clor[stac.top()]=frank;
					ans[frank]++;
				}
				clor[stac.top()]=frank;
				stac.pop();
				sta[a]=0;
				ans[frank]++;
			}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&value[i]);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		map[x].push_back(y);
	}
	   for(int i=1;i<=n;i++)
	    {
	        if (!vis[i]) Tarjan(i);
	    }
	    
	for(int i=1;i<=n;i++){
		for(int j=0;j<map[i].size();j++){
			if(clor[i]!=clor[map[i][j]])
			nmap[clor[i]].push_back(clor[j]);
		}
	}
		for(int i=1;i<=frank;i++){
			if(ans[i]>1){
				rasn++;
			}
		}
		for(int i=1;i<=n;i++){
			point[low[i]]+=value[i];
		}
	for(int i=1;i<=rasn;i++){
	if(travel[i]!=1) dfs(i);
	}
	printf("%d",real);
	return 0;
} 
2022/4/4 13:55
加载中...