P3387缩点模版40pts WAon#13 4 5 7 9
查看原帖
P3387缩点模版40pts WAon#13 4 5 7 9
1086931
bishenke_2008楼主2024/7/16 15:03

大佬求调,调了一上午没看出来问题在哪
谢谢神犇们!!!

#include<bits/stdc++.h>
using namespace std;
#define next Next
const int N=400005;

int n,m;
int a[N];
int cnt=1;
int head[N];
int next[N],ver[N];
int cnt_c=1;
int head_c[N];
int next_c[N],ver_c[N];
int in[N];
int num=0;
int top=0;
int st[N];
bool ins[N];
int res=0;
int sum[N];
int dfn[N],low[N];
bool c[N];
int scc[N];

void add(int u,int v){
	next[cnt]=head[u];
	ver[cnt]=v;
	head[u]=cnt++;
}

void add_c(int u,int v){
	next_c[cnt_c]=head_c[u];
	ver_c[cnt_c]=v;
	head_c[u]=cnt_c++;
	in[v]++;
}

void tarjan(int x){
	dfn[x]=low[x]=++num;
	st[++top]=x;
	ins[x]=true;
	for(int i=head[x];i;i=next[i]){
		int y=ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[ver[i]])
			low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		res++;
		int z;
		while(z!=x){
			z=st[top--];
			ins[z]=false;
			c[z]=res;
			scc[res]+=a[z];
		}	
	}
}

int topo(){
	int dp[N];
	queue<int> q;
	for(int i=1;i<=res;i++){
		dp[i]=scc[i];
		if(!in[i])
			q.push(i);
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head_c[x];i;i=next_c[i]){
			int y=ver_c[i];
			dp[y]=max(dp[y],dp[x]+sum[y]);
			in[y]--;
			if(!in[y])
				q.push(y);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,dp[i]);
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		if(u==v) continue;
		add(u,v);
	}
	
	for(int i=1;i<=n;i++)
		if(!dfn[i]){
			top=0;
			tarjan(i);
		}
	
	for(int x=1;x<=n;x++)
		for(int i=head[x];i;i=next[i]){
			int y=ver[i];
			if(c[x]==c[y]) continue;
			add_c(c[x],c[y]);
		}
	
	cout<<topo();
	return 0;
}
2024/7/16 15:03
加载中...