#3 #11求帮调 , dij+tarjan
查看原帖
#3 #11求帮调 , dij+tarjan
310726
Nagato_楼主2024/8/9 22:19
#include<bits/stdc++.h>
using namespace std;

int n , m , cbd , p , wine[500010] , w[500010]  , buy[500010] , b[500010] , ans;

int sv[500010], sc;

vector<int> scc[500010] , ms[500010] , ma[500010];
stack<int> s;

int v[500010] , dfn[500010] , low[500010] , dfncnt , ins[500010] ;

void tarjan(int x)
{
	dfn[x] = low[x] = ++dfncnt;
	v[x] = 1 , ins[x] = 1 ;
	s.push(x);
	
	for(int i:ma[x])
	{
		if(v[i])
		{
			if(ins[i])
				low[x] = min( low[x] , dfn[i] );  //wrong
			continue;
		}
		
		tarjan(i);
		
		low[x] = min(low[x] , low[i]);  //wrong
	}
	
	if(dfn[x] == low[x])
	{
		sc++;
		
		int p = -1;
		
		while( p != x )
		{
			p = s.top();
			s.pop();
			
			sv[p] = sc;
			scc[sc].push_back(p);
			
			b[sc] += buy[p];
			w[sc] = max(w[sc] , wine[p]);
			
			ins[p] = 0;
		}
	}
	
	return;
}

void set_edge()
{
	for(int i=1;i<=sc;i++)
	{
		memset(v,0,sizeof(v));
		
		for(int j:scc[i])
		{
			for(int t:ma[j])
			{
				if( v[t] || sv[t] == i )
					continue;
				
				ms[i].push_back( sv[t] );        //wrong
				v[t] = 1;
			}
		}
	}
}

struct node
{
	int u,d;
};

bool operator<(const node &x,const node &y)
{
	return x.d < y.d;
}

priority_queue<node> q;

int d[500010];

void dij()
{
	memset(v,0,sizeof(v));
	
	for(int i=1;i<=sc;i++)
		d[i] = -1000000000;
	
	d[ sv[cbd] ] = b[ sv[cbd] ];
	q.push( { sv[cbd] , b[ sv[cbd] ] } );
	

	
	while(!q.empty())
	{
		node p = q.top();
		q.pop();
		
		if(v[p.u])
			continue;
		
		v[ p.u ] = 1;
		
		for(auto t:ms[p.u])
		{
			if(v[t] || p.d + b[t] <= d[t] )
				continue;
			
			d[t] = p.d + b[t];
			q.push({ t , d[t] });
		}
	}
	
	return;
}

int main()
{	
	cin>>n>>m;

	for(int i=1,p1,p2;i<=m;i++)
	{
		cin>>p1>>p2;
		ma[p1].push_back(p2);
	}
	
	for(int i=1;i<=n;i++)
		cin>>buy[i];
		
	cin>>cbd>>p;
	
	for(int i=1,p1;i<=p;i++)
	{
		cin>>p1;
		wine[p1]=1;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
			tarjan(i);
	}
	
	set_edge();
	
	dij();
	
	for(int i=1;i<=sc;i++)
	{
		if(w[i])
			ans = max(ans,d[i]);
	}
	
	cout<<ans;
	
	return 0;
}
2024/8/9 22:19
加载中...