Solution

差分约束模板题

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 101000;
const int M = 500000;
int n, m;
int head[N], nex[M], to[M], val[M], ce;
void add(int u, int v, int w) {
    to[++ce] = v; nex[ce] = head[u];
    head[u] = ce; val[ce] = w;
}
queue<int> q;
int d[N], c[N], used[N];
bool spfa() {
    memset(d, -0x3f, sizeof d);
    c[n+1] = 1; d[n+1] = 0;
    q.push(n+1);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        used[u] = false;
        for(int i=head[u]; i; i=nex[i]) {
            int v = to[i], w = val[i];
            if(d[v] < d[u] + w) {
                d[v] = d[u] + w;
                if(!used[v]) {
                    used[v] = true;
                    if(++c[v] >= n) return false;
                    q.push(v);
                }
            }
        }
    }
    return true;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) {
        int k, x, y; scanf("%d%d%d", &k, &x, &y);
        switch(k) {
            case 1: add(x, y, 0); add(y, x, 0); break;
            case 2: add(x, y, 1); break;
            case 3: add(y, x, 0); break;
            case 4: add(y, x, 1); break;
            case 5: add(x, y, 0); break;
        }
    }
    for(int i=n; i>=1; i--) add(n+1, i, 1);
    if(!spfa()) puts("-1");
    else {
        long long ans = 0;
        for(int i=1; i<=n; i++) ans += d[i];
        printf("%lld\n", ans);
    }
    return 0;
}

Description

幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

Input

输入的第一行是两个整数N,K。
接下来K行,表示这些点需要满足的关系,每行3个数字,X,A,B。
如果X=1, 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多;
如果X=2, 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果;
如果X=3, 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果;
如果X=4, 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果;
如果X=5, 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果;

Output

输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出-1。

Sample Input

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

Sample Output

11

HINT

【数据范围】
对于30%的数据,保证 N<=100
对于100%的数据,保证 N<=100000
对于所有的数据,保证 K<=100000,1<=X<=5,1<=A, B<=N

Source

Day1