您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVALive 4885 Task：差分約束系統求可行解

編輯：C++ 入門

問題建模

有 n 個任務，m 個限制條件：

task i starts at least A minutes later than task j → i - j ≥ A → j - i ≤ -A
task i starts within A minutes of the starting time of task j → i - j ≤ A

目標：求任意一組滿足所有約束的任務開始時間，或判定無解。

差分約束與圖論轉換

將每個任務視為圖中的頂點，每個不等式 u - v ≤ C 轉化為一條從 v 指向 u、權重為 C 的有向邊。引入超級源點 0，向所有頂點連接權重 0 的邊（x_i - x_0 ≤ 0）。若圖中存在負環，則約束系統無解；否則從源點 0 運行 SPFA（或 Bellman-Ford）求得的最短路距離 dis[i] 即為一組可行解（可能為負），最後整體平移使最小值變為 1 即可輸出正整數時間。

代碼實現（SPFA 判負環 + 求解）

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

const int INF = 1e8;
const int N = 205;
const int M = 200005;

struct Edge { int from, to, dis, next; } edge[M];
int head[N], ecnt;
int n, m;
int dis[N], inq[N], cnt[N];

void init() { memset(head, -1, sizeof head); ecnt = 0; }
void addEdge(int u, int v, int d) {
    edge[ecnt] = {u, v, d, head[u]};
    head[u] = ecnt++;
}

bool spfa() {
    memset(dis, 0x3f, sizeof dis);
    memset(inq, 0, sizeof inq);
    memset(cnt, 0, sizeof cnt);
    dis[0] = 0;
    for (int i = 1; i <= n; ++i) addEdge(0, i, 0);
    queue<int> q;
    q.push(0);
    inq[0] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;
        for (int i = head[u]; ~i; i = edge[i].next) {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].dis) {
                dis[v] = dis[u] + edge[i].dis;
                if (!inq[v]) {
                    inq[v] = 1;
                    if (++cnt[v] > n) return false; // 負環
                    q.push(v);
                }
            }
        }
    }
    return true;
}

void build() {
    scanf("%d", &m);
    init();
    char op[20];
    int a, b, x;
    while (m--) {
        scanf("%s", op); // "task"
        scanf("%d", &a); // i
        scanf("%s", op); // "starts"
        if (op[0] == 'a') { // "at least"
            scanf("%d", &x);
            scanf("%s %s", op, op); // "minutes later than"
            scanf("%d", &b); // j
            addEdge(a, b, -x); // j - i <= -x  => i - j >= x
        } else { // "within"
            scanf("%d", &x);
            scanf("%s %s %s %s %s", op, op, op, op, op); // "minutes of the starting time of"
            scanf("%d", &b); // j
            addEdge(b, a, x); // i - j <= x
        }
        addEdge(a, b, 0); // 確保連通性
    }
}

void solve() {
    build();
    if (!spfa()) { puts("Impossible."); return; }
    int mn = dis[1];
    for (int i = 2; i <= n; ++i) mn = min(mn, dis[i]);
    mn = -mn + 1; // 平移到正數
    for (int i = 1; i <= n; ++i)
        printf("%d%c", dis[i] + mn, i == n ? '\n' : ' ');
}

int main() {
    while (scanf("%d", &n), n) solve();
    return 0;
}