萌新刚学OI,40分求助
查看原帖
萌新刚学OI,40分求助
253433
XeRnHe楼主2020/12/17 16:39

不知道为什么,六个点WA

代码:

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#define reg register
#define MAXN 10005
#define ll long long 
using namespace std;
ll n,m,dfsTime,sccCount;
ll pre[MAXN],low[MAXN],sccNo[MAXN],a[MAXN],in[MAXN],dp[MAXN];
vector<ll> adjtmp[MAXN];
vector<ll> adj[MAXN];
stack<ll> s;
void Tarjan(ll u){
	pre[u]=low[u]=++dfsTime;
	s.push(u);
	for(reg ll i=0;i<adjtmp[u].size();i++){
		ll v=adjtmp[u][i];
		if(pre[v]==0){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(sccNo[v]==0)
			low[u]=min(low[u],pre[v]);
	}
	if(pre[u]==low[u]){
		sccCount++;
		while(1){
			ll t=s.top();s.pop();
			sccNo[t]=sccCount;
			if(u==t)
				break;
			a[sccCount]+=a[t];
		}
	}
}
ll topo(){
	queue<ll> q;
	for(reg ll i=1;i<=sccCount;i++)
		if(in[i]==0){
			q.push(i);
			dp[i]=a[i];
		}
	while(!q.empty()){
		ll u=q.front();q.pop();
		for(reg ll i=0;i<adj[u].size();i++){
			ll v=adj[u][i];
			dp[v]=max(dp[v],dp[u]+a[v]);
			in[v]--;
			if(in[v]==0)
				q.push(v);
		}
	}
	ll ans=0;
	for(reg ll i=1;i<=sccCount;i++)
		ans=max(ans,dp[i]);
	return ans;
}
int main(){
	cin>>n>>m;
	for(reg ll i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(reg ll i=1;i<=m;i++){
		ll u,v;
		scanf("%lld%lld",&u,&v);
		adjtmp[u].push_back(v);
	}
	for(reg ll i=1;i<=n;i++)
		if(pre[i]==0)
			Tarjan(i);
	for(reg ll i=1;i<=n;i++){
		for(reg ll j=0;j<adjtmp[i].size();j++){
			ll v=adjtmp[i][j];
			if(sccNo[i]!=sccNo[v])
				adj[sccNo[i]].push_back(sccNo[v]),in[sccNo[i]]++;
		}
	}
	cout<<topo();
	return 0;
}
2020/12/17 16:39
加载中...