题解 ： https://xiaoxiaoh.blog.csdn.net/article/details/104294442

一、内容

银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。

我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 1。

现在对于 N 颗我们关注的恒星，有 M 对亮度之间的相对关系已经判明。

你的任务就是求出这 N 颗恒星的亮度值总和至少有多大。
输入格式

第一行给出两个整数 N 和 M。

之后 M 行，每行三个整数 T, A, B，表示一对恒星(A, B)之间的亮度关系。恒星的编号从 1 开始。

如果 T = 1，说明 A 和 B 亮度相等。
如果 T = 2，说明 A 的亮度小于 B 的亮度。
如果 T = 3，说明 A 的亮度不小于 B 的亮度。
如果 T = 4，说明 A 的亮度大于 B 的亮度。
如果 T = 5，说明 A 的亮度不大于 B 的亮度。

输出格式

输出一个整数表示结果。

若无解，则输出 -1。

数据范围

N≤100000,M≤100000

输入样例：

5 7 
1 1 2 
2 3 2 
4 4 1 
3 4 5 
5 4 5 
2 3 5 
4 5 1

输出样例：

11

二、思路

• 根据题目所给关系可以建立不等式：
  
  

三、代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, M = 6 * N;
struct E {int v, w, next;} e[M];
int n, m, a, b, x, len, h[N], sh[N], top, num, id[N], scc_cnt, stack[N], dfn[N], low[N], scc[N], d[N]; 
bool in_st[N], vis[N];
void add(int h[], int u, int v, int w) {
    e[++len].v = v; e[len].next = h[u]; e[len].w = w; h[u] = len; 
}
void tarjan(int u) {
    dfn[u] = low[u] = ++num;
    stack[++top] = u; in_st[u] = true;
    for (int j = h[u]; j; j = e[j].next) {
        int v = e[j].v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_st[v]) low[u] = min(low[u], dfn[v]);
    } 
    if (dfn[u] == low[u]) {
        ++scc_cnt; int v;
        do {
            v = stack[top--]; in_st[v] = false;
            scc[scc_cnt]++; id[v] = scc_cnt; 
        } while (u != v); 
    }
}
int dfs(int u) {
    int ans = 0;
    vis[u] = true;
    for (int j = h[u]; j; j = e[j].next) {
        int v = e[j].v;
        if (id[u] == id[v]) ans += e[j].w;
        if (vis[v] || id[u] != id[v]) continue;
        ans += dfs(v);
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) add(h, b, a, 0), add(h, a, b, 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 if (x == 5) add(h, a, b, 0);
    }
    //建立超级源点 
    for (int i = 1; i <= n; i++) add(h, 0, i, 1);
    tarjan(0);
    //判断是否有强连通分量 边权大于0
    bool ok = false;
    for (int i = 0; i <= n; i++) {
        if (dfs(i)) {
            ok = true; 
            break;
        }
    } 
    if (ok) printf("-1");
    else {
        for (int u = 0; u <= n; u++) {
            for (int j = h[u]; j; j = e[j].next) {
                int v = e[j].v;
                if (id[u] != id[v]) add(sh, id[u], id[v], e[j].w);
            }
        }
        //根据拓扑图进行dp
        for (int u = scc_cnt; u >= 1; u--) {
            for (int j = sh[u]; j; j = e[j].next) {
                int v = e[j].v;
                if (d[v] < d[u] + e[j].w) d[v] = d[u] + e[j].w;
            }
        }
        ll ans = 0;
        for (int i = 1; i <= scc_cnt; i++) ans += d[i] * scc[i];
        printf("%lld", ans); 
    }
    return 0; 
}