題意：和上一題比較像，不過這里不是根據已知的約束求出另外一個約束，而是判定是否存在解。給定一個區間的和值區間，問整個區間能否滿足所有的要求。

解法：虛擬一個超級源點，超級源點到點i的最短路表示到第i個數時總和為dis[i]，為了保證每個點能夠被計算到，那么需要從超級源點連一條沒有什么影響的邊出來。然后對整個圖求一次spfa，觀察是否存在負環。

代碼如下：

#include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;int N, M, idx; int head[105]; const int T = 102; // 超級源點 struct Edge {int v, ct, next; }e[505];void insert(int a, int b, int ct) {e[idx].v = b, e[idx].ct = ct;e[idx].next = head[a];head[a] = idx++; }#include <queue> int dis[105], cnt[105]; char vis[105];bool spfa() {memset(dis, 0x3f, sizeof (dis));memset(cnt, 0, sizeof (cnt));memset(vis, 0, sizeof (vis));queue<int>q;q.push(T);cnt[T] = 1, vis[T] = 1, dis[T] = 0;while (!q.empty()) {int v = q.front();q.pop();vis[v] = 0;if (cnt[v] > N+5) return false;for (int i = head[v]; i != -1; i = e[i].next) {if (dis[e[i].v] > dis[v] + e[i].ct) {dis[e[i].v] = dis[v] + e[i].ct;if (!vis[e[i].v]) {q.push(e[i].v);++cnt[e[i].v];vis[e[i].v] = 1;}} }}return true; }int main() {int a, b, c;char op[5];while (scanf("%d", &N), N) {idx = 0;memset(head, 0xff, sizeof (head));scanf("%d", &M);for (int i = 0; i < M; ++i) {scanf("%d %d %s %d", &a, &b, op, &c);if (op[0] == 'g') { // dis[b] - dis[a-1] >= c+1insert(a+b, a-1, -c-1);} else { // dis[b] - dis[a-1] <= c-1insert(a-1, a+b, c-1);}}for (int i = 0; i <= N; ++i) {insert(T, i, rand() % 1000);// 引入一條從超級源點到任意一點的0邊，這個約束條件對題解沒有影響 }if (spfa()) {puts("lamentable kingdom");} else {puts("successful conspiracy");}}return 0; }

?

轉載于:https://www.cnblogs.com/Lyush/archive/2013/03/14/2959416.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的POJ-1364 King 差分约束的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。