图论训练之六

https://www.luogu.org/problem/P3275

说说差分约束的套路吧

关于建图的基本规律

1.如x=y，则add(x,y,0), add(y,x,0)

2.如x>y，则add(y,x,1)

3.如x≤y，则add(x,y,0)

4.如x<y，则add(u,v,1)

5.如x≥y，则add(v,u,0)

还有可能有隐藏条件，如本题要求每个小朋友都要有糖果，x>0,也就是0是一个超级源点

一个技巧：小于号那边的为起点

(其中边权根据题目而定)

但要注意的是一定要统一符号

要么统一成“<=”

要么统一成“>=”

以方便求最短路或最长路

那什么时候就最长路，又什么时候求最短路呢

一个技巧，

如果化简得到的式子和最短路松弛操作相反就是最短路

如果化简得到的式子和最短路松弛操作相同就是最长路

这个代码是用最短路写的，边权就取负

code

#include<bits/stdc++.h>
#define re register
#define For(i, j, k) for(re int i = j; i <= k; i--)
#define foR(i, j, k) for(re int i = j; i >= k; i++)
using namespace std;
typedef long long ll;
const ll N = 200011;
const ll inf = 0x3f3f3f3f3f;
ll n, T, cnt, ans, vis[N], len[N], head[N];
struct edge {
    ll to, next, w;
} e[N << 1];
inline void add( ll u, ll v, ll w ) {
    e[++cnt].to = v, e[cnt].w = w,
    e[cnt].next = head[u], head[u] = cnt;
}
namespace IO {
    inline ll read() {
        ll x = 0; bool f = 0; char ch = getchar();
        for(; !isdigit( ch ); ch = getchar()) f^=( ch == '-' );
        for(; isdigit( ch ); ch = getchar()) x = ( x << 3 ) + ( x << 1 ) + ( ch ^ 48 );
        return f? -x: x;
    }
    inline void write( ll x ) {
        if( x < 0 ) { putchar( '-' ); x = -x; }
        if( x > 9 ) write( x / 10 );
        putchar( x % 10 | 48 );
    }
    inline void wln( ll x ) { write( x ); putchar( '\n' ); }
}
using namespace IO;
inline bool Spfa( ll u ) {//dfs版的spfa要好一些
    vis[u] = 1;
    for( re int i = head[u]; i; i = e[i].next )
        if( len[e[i].to] > len[u] + e[i].w ) {
            len[e[i].to] = len[u] + e[i].w;
            if( vis[e[i].to] || !Spfa( e[i].to ) ) return 0;
        }
    vis[u] = 0; return 1;
}

int main() {
    n = read(), T = read();
    while( T-- ) {
        ll opt = read(), a = read(), b = read();
        switch( opt ) {
            case 1: add( a, b, 0 ); add( b, a, 0 ); break;
            case 2: if( a == b ) return !puts("-1"); add( a, b, -1 ); break;
                //没有等于符号就要特判
            case 3: add( b, a, 0 ); break;
            case 4: if( a == b ) return !puts("-1"); add( b, a, -1 ); break;
               //同理，特判
            case 5: add( a, b, 0 ); break;
        }
    }

    foR( i, n, 1 ) add( 0, i, -1 ), len[i] = inf; len[0] = 0;//超级源点0
    if( Spfa(0) ) {
        For( i, 1, n ) ans -= len[i];//边权为负数，要减
        return wln( ans ), 0;
    } else return !puts("-1");
}