差分约束小结

/*
    ZOJ 2770 Burn the Linked Camp
    差分约束
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

const int MAXN = 1009;

struct Edge {
    int v, ne, c;
} G[MAXN*MAXN];
int head[MAXN], cnt;

int C[MAXN], S[MAXN], dis[MAXN];
int vis[MAXN], sum[MAXN];

int n, m;

inline void addE (int u, int v, int c) {
    G[++cnt].v = v, G[cnt].c = c, G[cnt].ne = head[u];
    head[u] = cnt;
}

inline int SPFA() {
    queue<int> Q;
    dis[n] = 0, vis[n] = 1;
    Q.push (n);
    while (!Q.empty() ) {
        int k = Q.front(); Q.pop();
        for (int i = head[k]; i; i = G[i].ne) {
            int v = G[i].v;
            if (dis[k] + G[i].c < dis[v]) {
                dis[v] = dis[k] + G[i].c;
                if (!vis[v]) Q.push (v), vis[v] = 1, sum[v]++;
                if (sum[v] >= n) return -1;
            }
        }
        vis[k] = 0;
    }
    return dis[n]-dis[0];
}

inline void init() {
    memset (head, 0, sizeof head);
    memset (sum, 0, sizeof sum);
    memset (vis, 0, sizeof vis);
    memset (dis, 1, sizeof dis);
    cnt = 0;
}

int main() {
    while (scanf ("%d %d", &n, &m) == 2) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf ("%d", &C[i]);
            S[i] = S[i - 1] + C[i];
            addE (i, i - 1, 0);
        }
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
                addE (i - 1, j, S[j] - S[i - 1]);
        for (int i = 1, l, r, num; i <= m; i++) {
            scanf ("%d %d %d", &l, &r, &num);
            addE (r, l - 1, -num);
        }
        int ans = SPFA();
        if (ans != -1) printf ("%d
", ans);
        else puts ("Bad Estimations");
    }
}

ZOJ 2770

ZOJ 1508 Intervals

/*
    ZOJ 1508 Intervals
    差分约束
*/
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;

const int MAXN = 500009;
struct edge {
    int v, ne, c;
} G[MAXN << 1];
int head[MAXN], cnt;

int dis[MAXN], vis[MAXN];
int n, m, mr, ml;

inline void addE (int u, int v, int c) {
    G[++cnt].v = v, G[cnt].c = c, G[cnt].ne = head[u];
    head[u] = cnt;
}
inline int SPFA() {
    queue<int> ql;
    ql.push (mr);
    vis[mr] = 1, dis[mr] = 0;
    while (!ql.empty() ) {
        int x = ql.front(); ql.pop();
        for (int i = head[x]; i; i = G[i].ne) {
            int v = G[i].v;
            if (dis[x] + G[i].c < dis[v]) {
                dis[v] = dis[x] + G[i].c;
                if (!vis[v]) vis[v] = 1, ql.push (v);
            }
        }
        vis[x] = 0;
    }
    return -dis[ml - 1];
}
inline void init() {
    memset (head, 0, sizeof head);
    memset (dis, 1, sizeof dis);
    mr = 0, ml = 0x7fffffff;
    cnt = 0;
}

int main() {
    while (scanf ("%d", &n) == 1) {
        init();
        for (int i = 1, l, r, num; i <= n; i++) {
            scanf ("%d %d %d", &l, &r, &num);
            addE (r, l - 1, -num);
            mr = max (mr, r), ml = min (ml, l);
        }
        for (int i = ml; i <= mr; i++)
            addE (i - 1, i, 1), addE (i, i - 1, 0);
        printf ("%d
", SPFA() );
    }
}

ZOJ 1508

ZOJ 1260 King

/*
    ZOJ 1060 King
    差分约束
*/
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
const int MAXN = 1009;

struct edge {
    int v, c, ne;
} G[MAXN*MAXN];
int head[MAXN], cnt;
int dis[MAXN], vis[MAXN], sum[MAXN];

int n, m;

inline void addE (int u, int v, int c) {
    G[++cnt].v = v, G[cnt].c = c, G[cnt].ne = head[u];
    head[u] = cnt;
}

inline void init() {
    memset (head, 0, sizeof head);
    memset (dis, 1, sizeof dis);
    memset (vis, 0, sizeof vis);
    memset (sum, 0, sizeof sum);
    cnt = 0;
}

inline bool SPFA() {
    queue<int> ql;
    dis[n] = 0;
    for(int i=1;i<=n;i++){
        ql.push(i),vis[i]=1;
    }
    while (!ql.empty() ) {
        int x = ql.front(); ql.pop();
        for (int i = head[x]; i; i = G[i].ne) {
            int v = G[i].v;
            if (dis[x] + G[i].c < dis[v]) {
                dis[v] = dis[x] + G[i].c;
                if (!vis[v]) vis[v] = 1, ql.push (v), sum[v]++;
                if (sum[v] > n) return 0;
            }
        }
        vis[x] = 0;
    }
    return 1;
}
int main() {
    char s[10];
    while (scanf ("%d", &n) == 1 && n) {
        scanf ("%d", &m);
        init();
        for (int i = 1, l, r, c; i <= m; i++) {
            scanf ("%d %d %s %d", &l, &r, s, &c);
            r = l + r;
            if (s[0] == 'g')     addE (r, l-1, -c - 1);
            else                addE (l-1, r, c - 1);
        }
        if (SPFA() ) puts ("lamentable kingdom");
        else puts ("successful conspiracy");
    }
}

ZOJ 1260

以上三题都是根据题意直接建图的基础题。

ZOJ 1420 Cashier Employment

/*
    ZOJ 1420 Cashier Employment
    差分约束
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

const int MAXN = 1009;
struct edge {
    int v, c, ne;
} G[MAXN<<4];
int head[MAXN], cnt;
int dis[MAXN], vis[MAXN], sum[MAXN];

int need[MAXN], join[MAXN], s[MAXN];
int  n, m;

inline void addE (int u, int v, int c) {
    G[++cnt].v = v, G[cnt].c = c, G[cnt].ne = head[u];
    head[u] = cnt;
}

inline void init() {
    memset (head, 0, sizeof head);
    memset (sum, 0, sizeof sum);
    memset (vis, 0, sizeof vis);
    memset (dis, 1, sizeof dis);
    cnt = 0;
}

inline bool SPFA() {
    queue<int> ql;
    dis[24] = 0;
    for (int i = 0; i <= 24; i++)
        ql.push (i), vis[i] = 1;
    while (!ql.empty() ) {
        int x = ql.front(); ql.pop();
        for (int i = head[x]; i; i = G[i].ne) {
            int v = G[i].v;
            if (dis[x] + G[i].c < dis[v]) {
                dis[v] = dis[x] + G[i].c;
                if (!vis[v]) vis[v] = 1, ql.push (v), sum[v]++;
                if (sum[v] >= 23) return 0;
            }
        }
        vis[x]=0;
    }
    return 1;
}

inline bool make (int ans) {
    init();
    addE (24, 0, -ans);
    for (int i = 1; i <= 24; i++) {
        addE (i, i - 1, 0);
        addE ( i - 1, i, join[i]);
    }
    for (int i = 9; i <= 24; i++)    addE (i, i - 8, -need[i]);
    for (int i = 1; i <= 8; i++) addE (i, i + 16, ans - need[i]);
    return SPFA();
}

int main() {
    int Case;
    scanf ("%d", &Case);
    while (Case--) {
        for (int i = 1; i <= 24; i++) scanf ("%d", &need[i]);
        scanf ("%d", &n);
        for (int i = 1, x; i <= n; i++) {
            scanf ("%d", &x);
            join[x+1]++;
        }
        int l = 0, r = n, last = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (make (mid) )
                last = mid, r = mid - 1;
            else
                l = mid + 1;
        }
        if (last != -1) printf ("%d
", last);
        else    puts ("No Solution");
    }
}

ZOJ 1420

这题考虑

　　令 need[i] 为第i时刻需要多少出纳员，

join[i]为第i时刻有多少人应聘

s[i]作为节点,同时代表着从0时刻到i时刻需要多少出纳员

二分需要的出纳员数ans

可以列出关系:

s[i]-s[i-1]>=0;

　 s[i]-s[i-1]<=join[i];

　 s[24]-f[0]<=ans;

　 s[i]-s[i-8]>=need,i>8;

　 s[i]+s[24]-f[i+16]>=need[i],i<=8;

ZOJ 1455 Schedule Problem

关键在于使图中所有结点连通。添加一个虚拟的任务0，要求在所有任务开始后开始。这时令0号任务的开时间为0，找到其它点的最短路径。

s[i]为任务i的开始时间，len[i]为任务I的持续时间

关系式

FAS u v s[u]+len[u]>=s[v];

　 FAF u v s[u]+len[u]>=s[v]+len[v];

　 SAF u v s[u]>=s[v]+len[v];

SAF u v s[u]>=s[v];

s[0]>=s[i]+len[i];

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

const int MAXN = 10009;
struct edge {
    int v, c, ne;
} G[MAXN << 4];
int head[MAXN], cnt;
int sum[MAXN], vis[MAXN], dis[MAXN];

int n;
int  Len[MAXN];

inline void addE (int u, int v, int c) {
    G[++cnt].v = v, G[cnt].c = c, G[cnt].ne = head[u];
    head[u] = cnt;
}

inline void init() {
    memset (head, 0, sizeof head);
    memset (sum, 0, sizeof sum);
    memset (vis, 0, sizeof vis);
    memset (dis, 1, sizeof dis);
    cnt = 0;
}
inline bool SPFA() {
    queue<int> ql;
    dis[0] = 0, vis[0] = 1, ql.push (0);
    while (!ql.empty() ) {
        int x = ql.front(); ql.pop();
        for (int i = head[x]; i; i = G[i].ne) {
            int v = G[i].v;
            if (dis[x] + G[i].c < dis[v]) {
                dis[v] = dis[x] + G[i].c;
                if (!vis[v]) vis[v] = 1, ql.push (v), sum[v]++;
                if (sum[v] >= n) return 0;
            }
        }
        vis[x] = 0;
    }
    return 1;
}
int main() {
    char s[10];
    int Cs = 0;
    while (scanf ("%d", &n) == 1 && n) {
        init();
        for (int i = 1; i <= n; i++) {
                scanf ("%d", &Len[i]);
                addE (0, i, -Len[i]);
        }
        int u, v;
        while (scanf ("%s", s) == 1 && s[0] != '#') {
            scanf ("%d %d", &u, &v);
            if (!strcmp (s, "FAS") ) addE (u, v, Len[u]);
            if (!strcmp (s, "FAF") ) addE (u, v, Len[u] - Len[v]);
            if (!strcmp (s, "SAF") ) addE (u, v, -Len[v]);
            if (!strcmp (s, "SAS") ) addE (u, v, 0);
        }
        printf ("Case %d:
", ++Cs);
        if (SPFA() ) {
            int t=~(1<<31);
            for (int i = 1; i <= n; i++) t=min(t,dis[i]);
            for (int i = 1; i <= n; i++)
                printf ("%d %d
", i, dis[i]-t);
        }
        else puts ("impossible");
        puts("");
    }
}

ZOJ 1455

POJ 3169 Layout

同样是简单的建图

令s[i]为第i头牛的位置:

有关系:

ML u v l s[v]-s[u]<=l;

MD u v l s[v]-s[u]>=l;

还有 s[i]-s[i-1]>=0;

/*
    POJ 3169 Layout
    差分约束
*/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1009;
struct edge {
    int v, c, ne;
} G[MAXN*MAXN];
int head[MAXN], cnt;
int sum[MAXN], vis[MAXN], dis[MAXN];

int n, ML, MD;

inline void addE (int u, int v, int c) {
    G[++cnt].v = v, G[cnt].c = c, G[cnt].ne = head[u];
    head[u] = cnt;
}

inline void init() {
    memset (vis, 0, sizeof vis);
    memset (head, 0, sizeof head);
    memset (dis, 1, sizeof dis);
    memset (sum, 0, sizeof sum);
    cnt = 0;
}

inline int SPFA() {
    queue<int> ql;
    dis[1] = 0, vis[1] = 1;
    ql.push (1);
    while (!ql.empty() ) {
        int x = ql.front(); ql.pop();
        for (int i = head[x]; i; i = G[i].ne) {
            int v = G[i].v;
            if (dis[x] + G[i].c < dis[v]) {
                dis[v] = dis[x] + G[i].c;
                if (!vis[v]) vis[v] = 1, ql.push (v), sum[v]++;
                if (sum[v] >= n) return -1;
            }
        }
        vis[x] = 0;
    }
    if (dis[n] == 0x01010101) return -2;
    return dis[n];
}

int main() {
    int u, v, c;
    init();
    scanf ("%d %d %d", &n, &ML, &MD);
    for (int i = 1; i <= ML; ++i) {
        scanf ("%d %d %d", &u, &v, &c);
        addE (u, v, c);
    }
    for (int i = 1; i <= MD; ++i) {
        scanf ("%d %d %d", &u, &v, &c);
        addE (v, u, -c);
    }
    for (int i = 2; i <= n; i++)
        addE (i, i - 1, 0);
    printf ("%d
", SPFA() );
}

POJ 3169

UVA 11478 Halum

题目说的也不是非常清楚,其实是求最小的非负边的最大值.

跟前面的题相比这道题的约束条件看起来就不那么明显了

先二分最短边为ans

令 s[i] 为点i改变的数

对每一条边u v c有 s[u]-s[v]>=ans-c;

对于用这样的关系建出的图,如果存在负环就是无解.

如果ans=最大边的情况下还没出现负环,那么最大值可以无限大

同理 ans=1的时候就有负环了,就是不能满足条件.

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int MAXN = 600;
struct edge {
    int v, c, ne;
} G[MAXN*MAXN];
int head[MAXN], cnt;
int vis[MAXN], sum[MAXN], dis[MAXN];

int n, m;

inline void add (int u, int v, int d) {
    G[++cnt].v = v, G[cnt].c = d, G[cnt].ne = head[u];
    head[u] = cnt;
}

inline bool SPFA() {
    memset (dis, 0, sizeof dis);
    queue<int> q;
    for (int i = 1; i <= n; i++)
        vis[i] = 1, sum[i] = 1,    q.push (i);
    while (!q.empty() ) {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for (int i = head[u]; i != 0; i = G[i].ne) {
            int v = G[i].v;
            if (dis[u] + G[i].c < dis[v]) {
                dis[v] = dis[u] + G[i].c;
                if (!vis[v]) q.push (v), vis[v] = 1;
                if (++sum[v] >= n)        return 0;
            }
        }
    }
    return true;
}

inline bool make (int x) {
    for (int i = 1; i <= cnt; i++)     G[i].c -= x;
    bool ok = SPFA();
    for (int i = 1; i <= cnt; i++)    G[i].c += x;
    return ok;
}

int  main() {
    while (~scanf ("%d%d", &n, &m) ) {
        memset (head, 0, sizeof (head) );
        cnt = 0;
        int u, v, x;
        for (int i = 0; i < m; i++) {
            scanf ("%d%d%d", &u, &v, &x);
            add (u, v, x);
        }
        if (make (10009) ) puts ("Infinite");
        else if (!make (1) ) puts ("No Solution");
        else {
            int l = 1, r = 10009, ans = 1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (make (mid) )
                    ans = mid, l = mid + 1;
                else
                    r = mid - 1;
            }
            printf ("%d
", ans);
        }
    }
}

uva 11478

小结:

总的来说，这类题需要先找到题目中的约束条件,一般来说有求最值,判断可行性这几种问题。

对于求最值的情况，根据图的定义如果是直接可以通过路径长度得到的话，需要注意起点的设计，最短路还是最长路。如果是需要通过枚举或者二分求的最值，需要注意可行性需要判断的是负环还是正环。

有时候需要添加额外的点，使整个图连通。或者根据求的路径的性质（最长，最短）赋好距离初值，然后只要将所有点加入队列就行。