有向图的强连通分量——银河（差分约束和强连通分量两种做法）

异世界转生入口：银河

差分约束思路：图里面有给定最小亮度，然后只需要按照输入关系去构造不同的边，最后建立一个超级源点和其他所有的点连一条长度为1的边就可以了，这里因为是求最小值所以要用求最长路的方法去求。

这道题的答案和差分约束——糖果_北岭山脚鼠鼠的博客-CSDN博客一模一样。

tarjan算法思路：

当x==1时，关系为 ：a>=b && b>=a,所以add(a,b,0),add(b,a,0)两条边；

当x==2时 ，为 b>=a+1,add(a,b,1)

当x==3时，为a>=b ,add(b,a,0)

当x==4时，为a>=b+1,add(b,a,1)

当x==5时，为b>=a, add(a,b,0) 

这题按照差分约束的思路来建边。

首先判定无解的情况，因为每一个节点的权值都必定是大于0的，所以无解的情况就是存在正环

使用tarjan算法来进行的建造强连通分量，在每一个强连通分量当中，都必定存在环，如果有某一条边的权值是大于0的，那么一定会存在正环，等同于x1>=x2>=x3>=x1+c,这种就是无解的情况。

有解当且仅当每一个强连通分量里面的边权都是0。

步骤1：走一遍tarjan算法

步骤2：缩点

步骤3：根据拓扑序递推，最后累加所有点上面的递推子就是答案。

代码:

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e5+10,M=6e5+10;
int n,m;
int h[N],hs[N],e[M],ne[M],w[M],idx;
int dfn[N],low[N],times;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,cnt[N];
int dist[N];
void add(int h[],int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++times;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }else if(in_stk[j])
        {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
 
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            cnt[scc_cnt]++;
        }while(y!=u);
    }
}
 
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    for(int i=1;i<=n;i++)
        add(h,0,i,1);
    while(m--)
    {
        int t,a,b;
        scanf("%d%d%d",&t,&a,&b);
        if(t==1) add(h,a,b,0), add(h,b,a,0);
        else if(t==2) add(h,a,b,1);
        else if(t==3) add(h,b,a,0);
        else if(t==4) add(h,b,a,1);
        else add(h,a,b,0);
    }
    tarjan(0);
    bool success=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)
            {
                if(w[j]>0) //在强连通分量里面找到了正环，无解。
                {
                    success=false;
                    break;
                }
            }else
            {
                add(hs,a,b,w[j]);
            }
        }
        if(!success) break;
    }
 
    if(!success) puts("-1");
    else
    {
        for(int i=scc_cnt;i;i--)
        {
            for(int j=hs[i];~j;j=ne[j])
            {
                int k=e[j];
                dist[k]=max(dist[k],dist[i]+w[j]);
            }
        }
        ll res=0;
        for(int i=1;i<=scc_cnt;i++)res+=(ll)dist[i]*cnt[i];
        printf("%lld\n",res);
    }
    return 0;
}