P3387 tarjan+topo80求调orz
  • 板块灌水区
  • 楼主DarkWing
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/3 22:25
  • 上次更新2024/8/4 09:01:12
查看原帖
P3387 tarjan+topo80求调orz
718203
DarkWing楼主2024/8/3 22:25

4和7两个点wa了,求大佬帮助

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+5,M=1e5+5;
int n,m;
int w[N],w1[N];
int h[N],ne[M],e[M],idx;
int hs[N];
int dfn[N],low[N],timestamp,scc_cnt;
int stk[N],top;
int in[N];
int id[N];
int dist[N];
bool vis[N][N];
bool is_stk[N];
void add(int h[],int u,int v)
{
	e[idx]=v;
	ne[idx]=h[u];
	h[u]=idx++;
}
void tarjan(int u)
{
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u;
	is_stk[u]=true;
//	cout<<1;
	for(int i=h[u];~i;i=ne[i])
	{
		int x=e[i];
		if(!dfn[x])
		{
			tarjan(x);
			low[u]=min(low[x],low[u]);
		}
		else
			if(is_stk[x])
				low[u]=min(low[u],dfn[x]);
	}
	if(dfn[u]==low[u])
	{
		int y;
		scc_cnt++;
		do
		{
			y=stk[top--];
			id[y]=scc_cnt;
			is_stk[y]=false;
			w1[scc_cnt]+=w[y];
		}while(u!=y);
	}
}
int topo()
{
	queue<int>q;
	for(int i=1;i<=scc_cnt;i++)
		if(in[i]==0)
		{
			q.push(i);
			dist[i]=w1[i];
		}
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
	//	cout<<2;
		for(int i=hs[x];~i;i=ne[i])
		{
			int y=e[i];
			dist[y]=max(dist[y],dist[x]+w1[y]);
			in[y]--;
			if(in[y]==0)
				q.push(y);
		}
	}
	int ans=0;
	for(int i=1;i<=scc_cnt;i++)
		ans=max(ans,dist[i]);
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add(h,u,v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	//cout<<scc_cnt<<' '<<id[1]<<' '<<id[2]<<endl;
	idx=0;
	memset(hs,-1,sizeof hs);
	for(int i=1;i<=n;i++)
	{
		for(int j=h[i];~j;j=ne[j])
		{
			int x=id[i],y=id[e[j]];
			if(x!=y&&!vis[x][y])
			{
			//	cout<<x<<' '<<y<<endl;
				vis[x][y]=true;
				add(hs,x,y);
				in[y]++;
			}
		}
	}
	cout<<topo();
	return 0;
}
2024/8/3 22:25
加载中...