模板求助
查看原帖
模板求助
234783
conprour楼主2021/2/25 11:31

RT,目前已知缩点部分大概没有问题,问题可能在存第二个图的地方左右。。。求大佬帮忙看看Orz\operatorname{Orz}

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+120,maxm=2e5+10;
int head[maxn],head1[maxn],dis[maxn],dfsn[maxn],low[maxn],stak[maxn],sum[maxn];
int n,m;
int cnt1,cnt2,cnt,tim,top;
int dp[maxn],ind[maxn],col[maxn];
struct edge
{
  int nxt,to;
}a[maxn],a1[maxn];
void add(int x,int y)
{
  a[++cnt1].nxt=head[x];
  head[x]=cnt1;
  a[cnt1].to=y;
}
void add1(int x,int y)
{
  a1[++cnt2].nxt=head1[x];
  head1[x]=cnt2;
  a1[cnt2].to=y;
}

void tarjan(int x)
{
  dfsn[x]=low[x]=++tim;
  stak[++top]=x;
  for(int i=head[x];i;i=a[i].nxt)
    {
      int v=a[i].to;
      if(!dfsn[v])
	{
	  tarjan(v);
	  low[x]=min(low[x],low[v]);
	}
      else if(!col[v])//在栈里(被遍历过但是还没确定属于哪一个强连通分量)
	{
	  low[x]=min(low[x],low[v]);
	}
    }
  if(dfsn[x]==low[x])
    {
      col[x]=++cnt;//cnt记录强连通分量个数
      
      sum[cnt]+=dis[x];
      while(stak[top]!=x) sum[cnt]+=dis[stak[top]],col[stak[top--]]=cnt;//
      //printf("%d\n",sum[cnt]);
      top--;
    }
  return;
}
void topo()
{
  queue<int> q;
  for(int i=1;i<=cnt;i++)
    if(!ind[i]) q.push(i);
  while(!q.empty())
    {
      int now=q.front();q.pop();
      for(int i=head1[now];i;i=a1[i].nxt)
	{
	  int v=a1[i].to;
	  dp[v]=max(dp[v],dp[now]+sum[v]);
	  ind[v]--;
	  if(!ind[v]) q.push(v);
	}
    }
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
    {
      scanf("%d",&dis[i]);
    }
  int u,v;
  for(int i=1;i<=m;i++)
    {
      scanf("%d%d",&u,&v);
      add(u,v);
    }
  for(int i=1;i<=n;i++)
    {
      if(!dfsn[i]) tarjan(i);
    }
  for(int i=1;i<=n;i++)
    for(int j=head[i];j;j=a[j].nxt)
      {
	v=a[j].to;
	if(col[i]!=col[v])
	  {
	    add1(col[i],col[v]);
	    ind[col[v]]++;
	  }
      }
  topo();
  int ans=0;
  for(int i=1;i<=cnt;i++)
    {
    ans=max(ans,dp[i]);
    // printf("%d\n",dp[i]);
    }
  printf("%d",ans);
  return 0;
}
2021/2/25 11:31
加载中...