省選專練APIO2009搶掠計劃

這個就是沒啥大變動的Tarjan

先跑個Tarjan，然後點就縮好了。

接着就搞一個SPFA就行了。

辣麼仁慈，起點與終點都給你了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
struct Front_star{
	int u,v,w,nxt;
}e[2000001],edge[2000001];
int cnt=0;
int first[2000001]={0};
void add(int u,int v,int w){
	cnt++;
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=first[u];
	first[u]=cnt;
} 
int n,m;
int low[2000001]={0};
int dfn[2000001]={0};
int siz[2000001]={0};
int color[2000001]={0};
int scc=0;
int tot=0;
int inqueue[2000001]={0};
stack<int> S;
int head[2000001]={0};
int ecnt=0;
void addedge(int u,int v,int w){
	ecnt++;
	edge[ecnt].u=u;
	edge[ecnt].v=v;
	edge[ecnt].w=w;
	edge[ecnt].nxt=head[u];
	head[u]=ecnt;
}
int rd[2000001]={0};
int cd[2000001]={0};
void tarjan(int u){
	tot++;
	dfn[u]=low[u]=tot;
	S.push(u);
	inqueue[u]=1;
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else{
			if(inqueue[v]){
				low[u]=min(low[u],dfn[v]);
			}
		}
	}
	if(low[u]==dfn[u]){
		scc++;
		int x;
		do{
			x=S.top();
			S.pop();
			color[x]=scc;
			siz[scc]++;
			inqueue[x]=0;
		}while(u!=x);
	}
}
queue<int> q;
int dis[2000001]={0};
void SPFA(){
	for(int i=1;i<=scc;i++){
		if(rd[i]==0){
			q.push(i);
			dis[i]=siz[i];
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].v;
			if(rd[v]==0)
				continue;
			rd[v]--;
			if(dis[v]<dis[x]+siz[v]){
				dis[v]=dis[x]+siz[v];
				
			}
			if(rd[v]==0){
				q.push(v);
			}
		}
	}
}
int a[2000001]={0};
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v,1);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		siz[color[i]]+=a[i]-1;
	}
	for(int i=1;i<=n;i++){
		for(int j=first[i];j;j=e[j].nxt){
			int u=i;
			int v=e[j].v;
			if(color[u]!=color[v]){
				addedge(color[u],color[v],1);
				rd[color[v]]++;
				cd[color[u]]++;
			}
		}
	}
	int s;
	memset(inqueue,0,sizeof(0));
	scanf("%d",&s);
//	SPFA();
//	cout<<"ecnt= "<<ecnt<<endl;
//	for(int i=1;i<=scc;i++){
//		cout<<siz[i]<<" ";
//	}
//	cout<<endl;
	q.push(color[s]);
	dis[color[s]]=siz[color[s]];
	while(!q.empty()){
//		cout<<"working!!"<<endl;
		int x=q.front();
		q.pop();
		inqueue[x]=0;
		for(int i=head[x];i;i=edge[i].nxt){
			int v=edge[i].v;
			if(dis[v]<dis[x]+siz[v]){
				dis[v]=dis[x]+siz[v];
				if(!inqueue[v]);
					q.push(v);
			}
		}
	}
	int ans=0;
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int ed;
		scanf("%d",&ed);
		ans=max(ans,dis[color[ed]]);
	}
	cout<<ans;
}