差分约束学习笔记

Cesare · 2019-02-28 15:37:43 · 题解

学习了差分约束。

差分约束的主要思想是什么？就我个人的理解，应该就是对于一张图，给出一些约束

条件，使这张图跑最短（长）路时不断接近想要的答案。

以上是我暂时的个人理解，记录一下。

例题一:小K的农场

先考虑他给出的约束条件:

2.a - b <= c

3.a = b

由此可以得出:

w( b, a ) = c

w( a, b ) = -c

w( a, b ) = w( b, a ) = 0

由于我们跑的是最长路，所以是 b -> a 连一条权值为 c 的边，最短路就反一下。

连边的实质其实就是是跑最短（长）路时得到的答案不断接近正确答案，就是给出约束条件。画一下图就很好理解了。

Code:

#include<bits/stdc++.h>
//#include"Bignum/bignum.h"
//#define lll bignum
#define ls(x) ( x << 1 )
#define rs(x) ( x << 1 | 1 )
//#define mid ( ( l + r ) >> 1 )
#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 = 100011;
const ll inf = 0x3f3f3f3f3f;

/*
    根据题面，先列出三条不等式。

    1.a - b >= c; -> w( b, a ) = c // a 比 b 大 c
    2.a - b <= c; -> w( a, b ) = -c // b 比 a 小 c
    3.a - b = 0; - > w( a, b ) = w( b, a ) = 0; // a 与 b 相等。

    为什么第二条不连 b -> a 呢？
    因为这与条件 1 矛盾。
    总之差分约束的所有条件都不能矛盾，且必须全部满足。
    挺抽象的，把它与跑 spfa 最长路拆开来理解应该会好些。
*/

ll n, T, cnt, len[N], vis[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 ) x = -x, putchar( '-' );
        if( x > 9 ) write( x / 10 );
        putchar( x % 10 | 48 );
    }

    inline void wln( ll x ) { write( x ); putchar( '\n' ); }

}

using namespace IO;

ll a, b, c;

inline bool Spfa( ll u ) {
    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] ) return 0; // 走过了，有环。 
            if( !Spfa( e[i].to ) ) return 0; // 递归到某一步走过了，有环。 
        }
    vis[u] = 0; // 回溯 
    return 1; // 没环 
}

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    n = read(), T = read();

    while( T-- ) {
        ll opt = read();
        switch( opt ) {
            case 1: a = read(), b = read(), c = read(); add( b, a, c ); break;
            case 2: a = read(), b = read(), c = read(); add( a, b, -c ); break;
            case 3: a = read(), b = read(); add( a, b, 0 ); add( b, a, 0 ); break;
        }
    } 

    For( i, 1, n ) add( 0, i, 0 ), len[i] = -inf;

    return puts( Spfa(0)? "Yes": "No" ), 0;
}

温馨提示:不要抄代码。

例题2:糖果

根据条件，我们得出五条不等式:

1.a - b = 0

2.a + 1 <= b

3.a >= b

4.a - 1 >= b

5.a <= b

进而得到:

w( a, b ) = w( b, a ) = 0

w( a, b ) = -1

w( b, a ) = 0

w( b, a ) = -1

w( a, b ) = 0

此处我们跑的是最短路，所以是 a -> b 连一条权值为 -1 的边，表示 a 比 b 小 1 。

记得用 dfs 模拟 Spfa 。

Code:

#include<bits/stdc++.h>
//#include"Bignum/bignum.h"
//#define lll bignum
#define ls(x) ( x << 1 )
#define rs(x) ( x << 1 | 1 )
//#define mid ( ( l + r ) >> 1 )
#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 ) {
    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() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    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;
//    For( i, 1, n ) cout<<"!"<<len[i]<<endl;
    if( Spfa(0) ) {
        For( i, 1, n ) ans -= len[i];
        return wln( ans ), 0;
    } else return !puts("-1");
}

温馨提示:不要抄代码。