传送门

题目的五个条件转化为差分约束的不等式
再加：

• 设d[0] = 0; d[i] – d[0] >= 1 每个星球最低为1亮度
• 再从0一个点往所有点连1的有向边

题目可能出现无解的情况，差分约束的图出现正环即无解。

但是题目数据量很大，直接在跑最长路的时候用spfa判正环会超时

先tarjan缩点。同一个强连通分量里面如果边权之和为正那么肯定存在正环直接无解。复杂度O(N)

最后把缩点后的图重新建图，是一个有向无环图，可以直接跑最长路。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 233;
int n, m;
int h[maxn], e[maxn], val[maxn], pre[maxn], cnt;
int hc[maxn], ec[maxn], valc[maxn], prec[maxn], cntc;
void add(int u, int v, int w)
{
    e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt;
}
void addc(int u, int v, int w)
{
    ec[++cntc] = v; valc[cntc] = w; prec[cntc] = hc[u]; hc[u] = cntc;
}
int dfn[maxn], low[maxn], c[maxn], stk[maxn], ins[maxn], num, top, cnum;
void tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    stk[++top] = x; ins[x] = 1;
    for(int i = h[x]; i; i = pre[i])
    {
        int y = e[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if(ins[y])
        {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if(dfn[x] == low[x])
    {
        cnum ++; int y;
        do{
            y = stk[top--];
            c[y] = cnum;
            ins[y] = 0;
        }while(y != x);
    }
}
int dis[maxn], vis[maxn];
void spfa(int s)
{
    queue<int> q;
    memset(dis, -1, sizeof dis);
    dis[s] = 0; q.push(s); vis[s] = 1;
    while(q.size())
    {
        int x = q.front(); q.pop(); vis[x] = 0;
        for(int i = hc[x]; i; i = prec[i])
        {
            int y = ec[i], z = valc[i];
            if(dis[y] < dis[x] + z )
            {
                dis[y] = dis[x] + z;
                if(!vis[y])
                {
                    q.push(y);
                    vis[y] = 1;
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int t, a, b;
        scanf("%d%d%d",&t, &a, &b);
        if(t == 1) add(a, b, 0), add(b, a, 0);
        else if(t == 2) add(a, b, 1);
        else if(t == 3) add(b, a, 0);
        else if(t == 4) add(b, a, 1);
        else add(a, b, 0);
    }
    for(int i = 1; i <= n; i++) add(0, i, 1);
    for(int i = 0; i <= n; i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    for(int x = 0; x <= n; x++)
    {
        for(int j = h[x]; j; j = pre[j])
        {
            int y = e[j];
            if(c[y] == c[x] && val[j] == 1)
            {
                cout<< -1;
                return 0;
            }
            if(c[y] != c[x])
            {
                addc(c[x], c[y], val[j]);
            }
        }
    }
    spfa(c[0]);
    ll ans = 0;
    for(int i = 0; i <= n; i++ ) ans += dis[c[i]];
    cout<<ans;
}