银河「建图 + Tarjan缩点 + 拓扑排序 + 最长路」

题目描述：

我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 1。现在对于 N 颗我们关注的恒星，有 M 对亮度之间的相对关系已经判明。你的任务就是求出这 N 颗恒星的亮度值总和至少有多大。

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

思路1「差分约束」：

最简单快捷的方式是SPFA跑差分约束

分析一下，最至少，转换成求最长路，用大于等于号来表示关系

分析五个条件建图：

• T = 1， A = B转换成A >= B, B >=A，也就是从A到B建一条权值为0的边，从B到A建一条权值为0的边
• T = 2,A < B,转换成B >= A + 1,从A到B建一条权值为1的边
• T = 3,A >= B,转换成A >= B + 0,从B到A建一条权值为0的边
• T = 4,A > B,转换成A >= B + 1,从B到A建一条权值为1的边
• T = 5,A <= B,转换成B >= A + 0,从A到B建一条权值为0的边

然后建一个超级源点0，跑SPFA就行，判掉正环为-1

特别要注意的是，建超级源点后，图的点其实就是n+1,通过最长路的边数判正环的时候不能写num[i] >= n，要改成num[i] > n

还有就是SPFA会被卡死，可以用SLF优化，快的飞起(太爱SLF优化了

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
int num[MAX];
void SPFA(){
    deque<int>q;
    for(int i = 1; i <= n; ++i){
        q.push_back(i);dis[i] = 1;vis[i] = 1;
    }
    while (!q.empty()) {
        int u = q.front();q.pop_front();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] < dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                num[v] = num[u] + 1;
                if(num[v] >= n){
                    cout << -1 << endl;
                    return;
                }
                if(!vis[v]){
                    if(dis[v] > dis[q.front()])q.push_front(v);
                    else q.push_back(v);
                    vis[v] = 1;
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        ans += dis[i];
    }
    cout << ans << endl;
}

void work(){
    cin >> n >> m;
    for(int i = 1, op, a, b; i <= m; ++i){
        cin >> op >> a >> b;
        if(op == 1){
            add(a, b, 0);
            add(b, a, 0);
        }
        else if(op == 2)add(a, b, 1);
        else if(op == 3)add(b, a, 0);
        else if(op == 4)add(b, a, 1);
        else add(a, b, 0);
    }
    SPFA();
}


int main(){
    io;
    work();
    return 0;
}

思路2「Tarjan缩点 + 拓扑排序 + 最长路」

如果数据很大，我们可以换个O(n)的方法做：

建图方法和上面一样

因为图的权值都是大于等于0的，我们可以考虑先缩点，形成一个个强连通分量后，如果任意一个强连通分量中存在权值不为0的边，那就一定存在正环，因为是强连通，每个点都可以到达任意一个点，那连通块中存在正权边，那就可以在里面转到死，形成正环

如果块内不存在正环，我们再进行拓扑排序找每个点的最长路，缩点后的入度为0的块塞到队列里面，这些点的亮度都初始化为1，利用拓扑排序来做一个小型的多源最长路的dp，每个块产生的价值就是块的大小乘以起点到该块的最长路

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int tmd;
int dfn[MAX], low[MAX];
bool vis[MAX];
int cnt;
int col[MAX];
int num[MAX];
int du[MAX];
stack<int>st;
void tarjan(int u){
    st.push(u);vis[u] = 1;
    dfn[u] = low[u] = ++tmd;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v])low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]){
        int now;
        ++cnt;
        do {
            now = st.top();
            st.pop();vis[now] = 0;
            col[now] = cnt;
            ++num[cnt];
        } while (now != u);
    }
}

vector<pii>G[MAX];
int dis[MAX];
void topu(){
    queue<int>q;
    for(int i = 1; i <= cnt; ++i){
        if(!du[i]){
            q.push(i);
            dis[i] = 1;
        }
    }
    ll ans = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();
        ans += dis[u] * num[u];
        for(auto [v, d] : G[u]){
            --du[v];
            if(!du[v])q.push(v);
            if(dis[v] < dis[u] + d){
                dis[v] = dis[u] + d;
            }
        }
    }
    cout << ans << endl;
}

void work(){
    cin >> n >> m;
    for(int i = 1, op, a, b; i <= m; ++i){
        cin >> op >> a >> b;
        if(op == 1){
            add(a, b, 0);
            add(b, a, 0);
        }
        else if(op == 2)add(a, b, 1);
        else if(op == 3)add(b, a, 0);
        else if(op == 4)add(b, a, 1);
        else add(a, b, 0);
    }
    for(int i = 1; i <= n; ++i){
        if(!dfn[i])tarjan(i);
    }
    for(int u = 1; u <= n; ++u){
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(col[u] == col[v]){
                if(tr[i].val != 0){
                    cout << -1 << endl;
                    return;
                }
            }
            else {
                G[col[u]].push_back(m_p(col[v], tr[i].val));
                ++du[col[v]];
            }
        }
    }
    topu();
}


int main(){
    io;
    work();
    return 0;
}