糖果

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2640 字
差分约束最长路栈优化SPFA
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1511
// 题意：N 个小朋友每人至少 1 颗糖，K 条约束（相等 / 小于 / 不小于 / 大于 / 不大于），求满足全部约束的最少糖果总数，无解输出 -1。
// 思路：差分约束求最长路。虚拟源点向每人连权 1 的边表示至少一颗糖，五种关系拆成若干条 x[v] >= x[u] + w 的边，出现正环即无解。
// 1. 关系是「A 不少于 B」时建 B -> A 权 0，「A 多于 B」时建 B -> A 权 1，方向写反会直接算错。
// 2. 用栈代替队列的 SPFA，并把虚拟源点的边按编号从大到小加入，能显著减少松弛轮数。
// 复杂度：O(k * (n + k)) 时间 / O(n + k) 空间
// 易错点：X = 2 和 X = 4 在 A == B 时必然矛盾，必须立即输出 -1，否则图上会出现自环。
// 易错点：答案是所有人的糖果数之和，最大可达 n^2 量级，累加必须用 long long。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Edge{
    int to;
    int w;
};
vector<Edge> g[MAXN];
long long dis[MAXN];
int cnt[MAXN];
bool inq[MAXN];
int main(){
    int n, k;
    if(!(cin >> n >> k)) return 0;
    for(int i = 0; i < k; i++){
        int x, a, b;
        cin >> x >> a >> b;
        if(x == 1){
            Edge p;
            p.to = b;
            p.w = 0;
            g[a].push_back(p);
            Edge q;
            q.to = a;
            q.w = 0;
            g[b].push_back(q);
        }
        else if(x == 2){
            if(a == b){
                cout << -1 << "\n";
                return 0;
            }
            Edge p;
            p.to = b;
            p.w = 1;
            g[a].push_back(p);
        }
        else if(x == 3){
            Edge p;
            p.to = a;
            p.w = 0;
            g[b].push_back(p);
        }
        else if(x == 4){
            if(a == b){
                cout << -1 << "\n";
                return 0;
            }
            Edge p;
            p.to = a;
            p.w = 1;
            g[b].push_back(p);
        }else{
            Edge p;
            p.to = b;
            p.w = 0;
            g[a].push_back(p);
        }
    }
    for(int i = n; i >= 1; i--){
        Edge p;
        p.to = i;
        p.w = 1;
        g[0].push_back(p);
    }
    stack<int> st;
    for(int i = 1; i <= n; i++){
        dis[i] = 0;
    }
    dis[0] = 0;
    inq[0] = true;
    st.push(0);
    while(!st.empty()){
        int u = st.top();
        st.pop();
        inq[u] = false;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].to;
            int w = g[u][i].w;
            if(dis[v] < dis[u] + w){
                dis[v] = dis[u] + w;
                cnt[v]++;
                if(cnt[v] > n + 1){
                    cout << -1 << "\n";
                    return 0;
                }
                if(!inq[v]){
                    inq[v] = true;
                    st.push(v);
                }
            }
        }
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        ans += dis[i];
    }
    cout << ans << "\n";
    return 0;
}
糖果

正文

一本通·提高篇的其它内容
