XVI Open Cup named after E.V. Pankratiev. GP of Eurasia--C.Inequalities

佚名 6年前 (2019-04-14) 随笔 1004人围观抢沙发百度已收录

给你若干二元不等式，求一组合法解

差分约束系统，使用最长路求解，需要用spfa看图里是否存在正权环，如果存在就无解

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)
const int N = 1e5 + 7;
typedef pair<int, int> P;
const int inf = 2e9;
int n, k, d[N], maxv[N], cnt[N], inq[N], q[N];
inline int readint() {
    char c = getchar();
    while (c == '\n' || c == ' ') c = getchar();
    int op = 1, x = 0;
    if (c == '-') op = -1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * op;
}
int ehead[N], tot = 0;
struct  edge {
    int v, cost, next;
}e[N << 2];
int main() {
    scanf("%d%d", &n, &k);
    rep(i, 0, k) d[i] = -inf, maxv[i] = inf;
    bool ok = 1;
    auto add = [&](int u, int v, int w) {
        ++ tot;
        e[tot].next = ehead[u];
        e[tot].v = v;
        e[tot].cost = w;
        ehead[u] = tot;
    };
    rep(i, 1, n) {
        int op, t1, x1, t2, x2;
        op = readint(); t1 = readint(); x1 = readint(); t2 = readint(); x2 = readint();
        if (t1 == 0 && t2 == 0) { // v[x1] + op <= v[x2]
            add(x1, x2, op);
        }
        else if (t1 == 0 && t2 == 1) { // v[x1] + op <= x2
            maxv[x1] = min(maxv[x1], x2 - op);
        }
        else if (t1 == 1 && t2 == 0) { // x1 + op <= v[x2]
            d[x2] = max(d[x2], x1 + op);
        }
        else { // x1 + op <= x2
            if (x1 + op > x2) ok = 0;
        }
    }
    if (!ok) {
        printf("NO\n");
        return 0;
    }
    int head = 0, tail = 0;
    auto push_back = [&](int x) {
        q[tail ++] = x; if (tail == N) tail = 0;
    };
    auto push_front = [&](int x) {
        if (head == 0) head = N - 1; else head --;
        q[head] = x;
    };
    auto pop = [&]() -> int {
        int t = q[head]; head ++; if (head == N) head = 0;
        return t;
    };
    rep(i, 1, k) inq[i] = 1, push_back(i);
    auto spfa = [&]() -> bool {
        while (head != tail) {
            int u = pop(); inq[u] = 0;
            for (int i = ehead[u]; i; i = e[i].next) {
                int v = e[i].v;
                if (d[v] < d[u] + e[i].cost) {
                    d[v] = d[u] + e[i].cost;
                    if (d[v] > maxv[v]) return 0;
                    if (!inq[v]) {
                        inq[v] = 1;
                        cnt[v] ++;
                        if (cnt[v] >= n) return 0;
                        // if (e[i].cost == 0) push_front(v);
                        // else push_back(v);
                        push_front(v);
                    }
                }
            }
        }
        return 1;
    };
    bool flag = spfa();
    if (!flag) {
        printf("NO\n"); return 0;
    }
    printf("YES\n");
    rep(i, 1, k) printf("%d\n", d[i]);
}
/*
2 2
1 0 1 0 2
0 0 2 0 1
3 2 
1 0 1 0 2 
0 1 5 0 1 
0 0 2 1 7
*/