红色一片
查看原帖
红色一片
420137
一月气聚楼主2021/12/26 19:09

来个好心人救救孩子吧

#include<bits/stdc++.h>
using namespace std;

const int maxn=10000+15;
int n,m,tim,stac[maxn],top;
int sd[maxn],p[maxn];//tarjan后的点  点权 
int dfn[maxn];//时间戳
int low[maxn];//tarjan到的点i及其子树中最早的搜索时间
int inque[maxn],en,enn; 
int vis[maxn];//记录是否还在栈中 
int dis[maxn];
int head[maxn],h[maxn]; //缩点前 缩点后 

struct EDGE{
	int to,from,nxt;
}edge[maxn*10],ed[maxn*10]; //缩点前 缩点后 

void add_edge(int x,int y){
	edge[++enn].from=x;
	edge[enn].to=y;
	ed[enn].nxt=head[x];
	head[x]=enn;
}

void tarjan(int x){ //本质上是个dfs 
	low[x]=dfn[x]=++tim;
	stac[++top]=x; vis[x]=1;
	for(int i=head[x]; i; i=edge[i].nxt){
		int v=edge[i].to;
		if(!dfn[v]) {
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		  else if(vis[v])
		     low[x]=min(low[x],low[v]);
	}
	if(dfn[x]==low[x]){ //出现了!强连通分量! 
		int y;
		while(y=stac[top--]){
			
			sd[y]=x; //和并查集差不多 
			vis[y]=0; 
			if(x==y) break; //环到头了 
			p[x]+=p[y];
		}
	}
}

int topo()
{
	queue <int> q;
	int tot=0;
	for(int i=1;i<=n;++i)
	  if(sd[i]==i && !inque[i]){
	  	q.push(i);
		dis[i]=p[i];
	  }   
	while(!q.empty()){
		int k=q.front(); q.pop();
		for(int i=h[k]; i; i=ed[i].nxt){
			int v=ed[i].to;
			dis[v]=max(dis[v],dis[k]+p[v]);
			inque[v]--;
			if(inque[v]==0) q.push(v);
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i)
	  ans=max(ans,dis[i]);
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&p[i]);
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);
	}
	for(int i=1;i<=n;++i)
	  if(!dfn[i]) tarjan(i);
	for(int i=1;i<=m;++i){
		int x=sd[edge[i].from],y=sd[edge[i].to];
		if(x!=y){//缩出的点之间连边 
			ed[++en].from=x;
			ed[en].to=y;
			ed[en].nxt=h[x];
			h[x]=en;
			inque[y]++;
		}
	}
	printf("%d",topo());
	return 0;
}
2021/12/26 19:09
加载中...