本文共 1807 字，大约阅读时间需要 6 分钟。

恒星的亮度

解题思路

先缩点

AC代码

#include
   
    #include
    
     #include
     
      using namespace std;long long n,m,ans,tot,tot1,top,T,TT;long long f[1000005],ru[1000005],dfn[1000005],low[1000005],col[1000005],sum[1000005],stak[1000005],head[1000005],head1[1000005];queue
      
       q; struct node{
   	long long to,next,w;}a[1000005],b[1000005];void add(long long x,long long y,long long z){
   	a[++tot]=(node){
   y,head[x],z};	head[x]=tot;}void add1(long long x,long long y,long long z){
   	b[++tot1]=(node){
   y,head1[x],z};	head1[x]=tot1;}void Tarjan(long long x)//求前连通分量缩点{
   	dfn[x]=low[x]=++T;	stak[++top]=x;	for(long long i=head[x];i;i=a[i].next)	{
   		long long v=a[i].to;		if(!dfn[v])		{
   			Tarjan(v);			low[x]=min(low[x],low[v]);		}		else if(!col[v])low[x]=min(low[x],low[v]);	}	if(dfn[x]==low[x])	{
   		col[x]=++TT;		sum[TT]++;		while(stak[top]!=x)		 sum[TT]++,col[stak[top--]]=TT;		top--;	}	return;}int main(){
   	scanf("%lld%lld",&n,&m);	for(long long i=1;i<=m;i++)//建表	{
   		long long t,x,y;		scanf("%lld%lld%lld",&t,&x,&y);		if(t==1)add(x,y,0),add(y,x,0);		if(t==2)add(x,y,1);		if(t==3)add(y,x,0);		if(t==4)add(y,x,1);		if(t==5)add(x,y,0);	}	for(long long i=1;i<=n;i++)	 if(!dfn[i])Tarjan(i);	for(long long i=1;i<=n;i++)	 for(long long j=head[i];j;j=a[j].next)//枚举	 {
   	 	long long v=a[j].to;	 	if(col[i]!=col[v])	 	 add1(col[i],col[v],a[j].w),ru[col[v]]++;	 	else if(a[j].w==1)	 	{
   	 		printf("-1");	 		return 0;		}	 }	for(long long i=1;i<=TT;i++)	{
   		f[i]=1;		if(!ru[i])q.push(i);	}	while(!q.empty())//dij	{
   		long long x=q.front();		q.pop();		ans+=f[x]*sum[x];		for(long long i=head1[x];i;i=b[i].next)		{
   			long long v=b[i].to;			ru[v]--;			f[v]=max(f[v],f[x]+b[i].w);			if(!ru[v])q.push(v);		}	}	printf("%lld",ans);	return 0;}
      
     
    
   

谢谢

转载地址：https://blog.csdn.net/weixin_45524309/article/details/117474467 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！