AcWing 368. 银河

解题报告：这题其实可以差分约束做。但是spfa跑太慢了，我们今天来讲一个线性的做法，tarjan，因为图中没有负点，如果图中存在正环就说明存在和为正数的强联通分量，然后最后问的所有亮度和，可以求出每个连通分量的个数再乘以亮度，亮度可以跑在长路，按照拓扑序的做法。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const   int N=100010,M=600010;
typedef long long ll;
int h[N],hs[N],e[M],ne[M],idx,w[M];
int dfn[N],low[N],s[N];
bool is[N];
int id[N],Size[N];
int n,m;
int dist[N];
int timestamp,top,ssc_cnt;
void add(int h[],int a,int b,int c)
{
   
   w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++ ;
}
void targin(int u)
{
   
    dfn[u]=low[u]=++timestamp;
    s[++top]=u,is[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
   
        int j=e[i];
        if(!dfn[j])
        {
   
            targin(j);
            low[u]=min(low[u],low[j]);
        }
        else if(is[j])
        {
   
            low[u]=min(low[u],dfn[j]);
        }
        
    }
    if(low[u]==dfn[u])
    {
   
        ++ssc_cnt;
        int y;
        do{
   
            y=s[top--];
            id[y]=ssc_cnt;
            Size[ssc_cnt]++;
            is[y]=false;
        }while(y!=u);
    }
}
int main()
{
   
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    while(m--)
    {
   
        int x,a,b;
        cin>>x>>a>>b;
        if(x==1)
        add(h,a,b,0),add(h,b,a,0);
        else if(x==2)
        add(h,a,b,1);
        else if(x==3)
        add(h,b,a,0);
        else if(x==4)
        add(h,b,a,1);
        else add(h,a,b,0);
    }
    for(int i=1;i<=n;i++)
    add(h,0,i,1);
    targin(0);
   // cout<<ssc_cnt<<endl;
    bool flag=true;
    for(int i=0;i<=n;i++)
    {
   
        for(int j=h[i];~j;j=ne[j])
    {
   
        int k=e[j];
        int a=id[i],b=id[k];
        if(a!=b)
        add(hs,a,b,w[j]);
        if(a==b&&w[j])
        {
   
            flag=0;
            break;
        }
    }
        if(!flag)
        break;
    }
    if(!flag)
    {
   
        cout<<-1<<endl;
        return 0;
    }
    ll res=0;
    for(int i=ssc_cnt;i;i--)
    for(int j=hs[i];~j;j=ne[j])
    {
   
        int k=e[j];
        if(dist[k]<dist[i]+w[j])
        {
   
            dist[k]=dist[i]+w[j];
        }
    }
    for(int i=1;i<=ssc_cnt;i++)
    res+=(ll)dist[i]*Size[i];
    cout<<res<<endl;
    return 0;
}