【ybt】【图论强连通课过例4】恒星的亮度

本文主要是介绍【ybt】【图论强连通课过例4】恒星的亮度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

恒星的亮度

题目链接：恒星的亮度

题目描述

在这里插入图片描述

解题思路

我们可以先从小向大建边，然后缩点。

如果缩点后同一集合内有两个点是小于的关系，那么不符合题意，无解。

再用贪心的思想拓扑，累加答案即可。

code

#include<iostream>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;queue<int> q;int n,m;
int tm,tt,ans;
int v[1000010];
int ru[1000010];
int az[1000010];
int dfn[1000010];
int low[1000010];
int num[1000010];
int dis[1000010];
int dui[1000010],top;
int hd[1000010],tot;
int hd1[1000010],tot1;struct abc{int to,nxt,w;
}b[1000010],b1[1000010];void add(int x,int y,int z)
{b[++tot]=(abc){y,hd[x],z};hd[x]=tot;
}void add1(int x,int y,int z)
{b1[++tot1]=(abc){y,hd1[x],z};hd1[x]=tot1;
}void tarjan(int x)
{dfn[x]=low[x]=++tm;dui[++top]=x;az[x]=1;for(int i=hd[x];i;i=b[i].nxt){int y=b[i].to;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(az[y])low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){v[x]=++tt;num[tt]++;az[x]=0;while(dui[top]!=x){v[dui[top]]=tt;az[dui[top]]=0;num[tt]++;top--;}top--;}
}signed main()
{cin>>n>>m;for(int i=1;i<=m;i++){int t,a,b;scanf("%lld%lld%lld",&t,&a,&b);if(t==1)add(a,b,0),add(b,a,0);if(t==2)add(a,b,1);if(t==3)add(b,a,0);if(t==4)add(b,a,1);if(t==5)add(a,b,0);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)for(int j=hd[i];j;j=b[j].nxt){int y=b[j].to;if(v[i]!=v[y])add1(v[i],v[y],b[j].w),ru[v[y]]++;else if(b[j].w==1){printf("-1");return 0;}}for(int i=1;i<=tt;i++){dis[i]=1;if(!ru[i])q.push(i);}while(!q.empty()){int x=q.front();q.pop();ans+=dis[x]*num[x];for(int i=hd1[x];i;i=b1[i].nxt){int y=b1[i].to;ru[y]--;dis[y]=max(dis[y],dis[x]+b1[i].w);if(!ru[y])q.push(y);}}cout<<ans<<endl;
}