[SCOI 2011]糖果

Description

题库链接

给出 (N) 个节点，节点有正点权， (K) 个三元组 ((X,A,B)) 来描述节点点权之间的关系。

如果 (X=1) ，表示 (A) 的点权必须和 (B) 的点权相等；
如果 (X=2) ，表示 (A) 的点权必须小于 (B) 的点权；
如果 (X=3) ，表示 (A) 的点权必须不小于 (B) 的点权；
如果 (X=4) ，表示 (A) 的点权必须大于 (B) 的点权；
如果 (X=5) ，表示 (A) 的点权必须不大于 (B) 的点权

问如何安排点权使点权和最小。

(1leq N,Kleq 100000)

Solution

很显然是一个差分约束系统的模型。但值得注意的是由于题目是求最小值，所以构建的差分约束系统应该是建立在“最长路”的基础上的，所以不等号要用 ('geq') 。

对于建图，我们记连一条有向边从 (u) 到 (v) 边权为 (c) 为 ((u,v,c)) 。对于题中的五种情况：

如果 (X=1) ， ((u,v,0), (v,u,0)) ；
如果 (X=2) ， ((u,v,1)) ；
如果 (X=3) ， ((v,u,0)) ；
如果 (X=4) ， ((v,u,1)) ；
如果 (X=5) ， ((u,v,0))

然后依旧是 (dfs-SPFA) 来做，但是好像卡 (SPFA) ，好像将超级源点建边顺序取反就好了...

Code

//It is made by Awson on 2018.2.4
#include <bits/stdc++.h>
#define LL long long 
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('
'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 100000;
void read(int &x) {
    char ch; bool flag = 0;
    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
    x *= 1-2*flag;
}
void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n, k, x, u, v;
struct tt {int to, next, cost; }edge[(N<<2)+5];
int path[N+5], top, vis[N+5], dist[N+5];
void add(int u, int v, int c) {
    edge[++top].to = v, edge[top].cost = c, edge[top].next = path[u], path[u] = top; 
} 

bool dfs(int u) {
    vis[u] = 1;
    for (int i = path[u]; i; i = edge[i].next)
        if (dist[edge[i].to] < dist[u]+edge[i].cost) {
            if (vis[edge[i].to] != 0) return true;
            dist[edge[i].to] = dist[u]+edge[i].cost;
            if (dfs(edge[i].to)) return true;
        }
    vis[u] = 0;
    return false;
}
void work() {
    read(n), read(k);
    for (int i = n; i >= 1; i--) add(0, i, 1); 
    for (int i = 1; i <= k; i++) {
        read(x), read(u), read(v);
        if (x == 1) add(u, v, 0), add(v, u, 0);
        else if (x == 2) add(u, v, 1);
        else if (x == 3) add(v, u, 0);
        else if (x == 4) add(v, u, 1);
        else add(u, v, 0);
    }
    if (dfs(0)) {puts("-1"); return; }
    LL ans = 0;
    for (int i = 1; i <= n; i++) ans += dist[i];
    writeln(ans);
}
int main() {
    work(); return 0;
}