HDU4598 Difference（差分限制）

題意：

有一個圖，給圖上每個頂點都賦一個實數Ai。如果存在一個正整數T滿足下面兩個條件，這個圖就是一個"difference"。

1. |Ai| <= T。

2. 如果點i，j構成的邊在圖中存在，則 |Ai - Aj| >= T；否則 |Ai - Aj| < T。（"<=>" 代表充要條件）

給出圖，問這個圖是否是一個"difference"。

思路：

結合前兩個條件，顯然每條邊的兩個端點值都要一正一負，用dfs給每個頂點打上标記colors（1表示值為正，2表示值為負）。

如果圖中存在奇數邊的環一定無解，可以在dfs的時候進行剪枝，能夠讓運作時間快一大半。

然後是周遊每個點對（i，j），有下面四種情況：

1. 邊ij存在，且點i為正，則 Ai - Aj >= T

2. 邊ij存在，且點i為負，則 Aj - Ai >= T

3. 邊ij不存在，且點i為正，則 Ai - Aj <= T - 1

4. 邊ij不存在，且點i為負，則 Aj - Ai <= T - 1

僅僅是上面的不等式建的圖不一定連通，我們可以增加超級源點0，設A0 = 0，那麼就有下面兩種情況：

1. 點i為正時，0 <= Ai - A0 <= T - 1

2. 點i為負時，0 <= A0 - Ai <= T - 1

T的值不重要，取超過點數即可。

用上面兩組不等式建圖，然後spfa判負環即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <cstdlib>
#include <set>
#include <string>
#include <time.h>

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
struct edg{
    int v, w, nxt;
}G[90005];
int tot, pre[305];
void add(int u, int v, int w) {
    G[tot].v = v;
    G[tot].w = w;
    G[tot].nxt = pre[u];
    pre[u] = tot++;
}
int g[305][305], flag, n, times[305], colors[305], dis[305];
bool vis[305];
void dfs(int x, int k) {
    if (flag) {
        return;
    }
    colors[x] = k;
    vis[x] = true;
    for (int i = 1; i <= n; ++i) {
        if (g[x][i]) {
            if (!colors[i]) {
                dfs(i, 3 - k);
            } else {
                int t = (k + colors[i]) % 2;
                if (!t) {
                    flag = 1;
                }
            }
        }
        if (flag) {
            return ;
        }
    }
}
bool spfa() {
    for (int i = 1; i <= n; ++i) {
        dis[i] = inf;
        vis[i] = false;
        times[i] = 0;
    }
    times[0] = 1;
    vis[0] = true;
    dis[0] = 0;
    queue<int> que;
    que.push(0);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        for (int i = pre[u]; ~i; i = G[i].nxt) {
            int v = G[i].v, w = G[i].w;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    if (++times[v] > n + 1) { // 帶上0有n+1個點
                        return false;
                    }
                    vis[v] = true;
                    que.push(v);
                }
            }
        }
    }
    return true;
}
int main(){
    int t, T = 305;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                scanf("%1d", &g[i][j]);
            }
        }
        flag = 0;
        memset(colors, 0, sizeof(colors));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i) {
            if (!vis[i]) {
                dfs(i, 1);
            }
            if (flag) break;
        }
        if (flag) {
            puts("No");
            continue;
        }
        tot = 0;
        memset(pre, -1, sizeof(pre));
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (g[i][j]) {
                    if (colors[i] == 1) {
                        add(i, j, -T);           // Ai - Aj >= T
                    } else {
                        add(j, i, -T);           // Aj - Ai >= T
                    }
                } else {
                    if (colors[i] == 1) {
                        add(j, i, T - 1);       // Ai - Aj <= T - 1
                    } else {
                        add(i, j, T - 1);       // Aj - Ai <= T - 1
                    }
                }
            }
            if (colors[i] == 1) {
                add(0, i, T - 1);               // Ai - A0 <= T - 1
                add(i, 0, 0);                   // Ai - A0 >= 0
            } else {
                add(i, 0, T - 1);               // A0 - Ai <= T - 1
                add(0, i, 0);                   // Ai - A0 <= 0
            }
        }
        puts(spfa() ? "Yes" : "No");
    }
    return 0;
}
           

這道題隻用差分限制，不寫判奇環也能過，但時間要慢一些。下面一個是帶剪枝的，上面一個是不判奇環的。