題意：告訴我們一系列的不等式，當(dāng)然這些不等式都是兩個(gè)變量之間的差值，而非和值。劉備擁有N個(gè)軍營(yíng)，每個(gè)軍營(yíng)都有一個(gè)人數(shù)的上限，現(xiàn)在陸遜的探子來報(bào)劉備的[a, b]軍營(yíng)總?cè)藬?shù)不低過某一個(gè)值，現(xiàn)在問根據(jù)這些答案陸遜是否能夠正確推斷出劉備至少在各營(yíng)一共駐扎了多少部隊(duì)，如果不能推出，輸出“Bad Estimations”。

分析：根據(jù)給定的條件，我們?cè)O(shè)sum[i]表示劉備前i個(gè)軍營(yíng)一共駐扎了多少人，那么每個(gè)軍營(yíng)至多有多少人就能夠通過不等式列出來。假設(shè)一共有三個(gè)軍營(yíng)，上限分別為A,B,C，那么有：
0 <= sum[1] - sum[0] <= A
0 <= sum[2] - sum[1] <= B
0 <= sum[3] - sum[2] <= C
而對(duì)于陸遜的探子信息，對(duì)[a, b]不少于K人轉(zhuǎn)化為：
sum[b] - sum[a] >= K
將sum[x]看做是最短路里面的dis[x]那么根據(jù)滿足的三角不等式，就能夠推出圖的邊，我們也就能求解出一組合法的滿足所有等式的結(jié)果。
接下來要求的劉備總共至少駐扎了多少部隊(duì)，及設(shè)要求的量為M，則滿足
sum[N] - sum[0] >= M ?或 ?sum[0] - sum[N] <= -M
對(duì)于后面的不等式如果設(shè)sum[M] = 0，就變成了從N到0的最短路徑求解。

代碼如下：

#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <queue> #include <algorithm> using namespace std;int N, M, idx, head[1005]; long long sum[1005]; char vis[1005]; int cnt[1005]; long long dis[1005]; struct Edge {int v, next;long long ct; }e[1050005];void insert(int a, int b, long long ct) {e[idx].v = b, e[idx].ct = ct;e[idx].next = head[a];head[a] = idx++; }void build() {for (int i = 1; i <= N; ++i) { insert(i-1, i, sum[i] - sum[i-1]);insert(i, i-1, 0);} }bool spfa() {memset(cnt, 0, sizeof (cnt));memset(vis, 0, sizeof (vis));memset(dis, 0x3f, sizeof (dis));dis[N] = 0, vis[N] = 1;cnt[N] = 1;queue<int>q;q.push(N);while (!q.empty()) {int v = q.front();q.pop();vis[v] = 0;if (cnt[v] > N) 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;while (scanf("%d %d", &N, &M) == 2) {idx = 0;memset(head, 0xff, sizeof (head));for (int i = 1; i <= N; ++i) {scanf("%I64d", &sum[i]);sum[i] += sum[i-1]; // 求一個(gè)前綴和 }for (int i = 0; i < M; ++i) {scanf("%d %d %d", &a, &b, &c);insert(b, a-1, -c); // 將a, b, c轉(zhuǎn)化為圖中的邊 }build();if (spfa()) {printf("%d\n", -dis[0]);} else {puts("Bad Estimations");}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Lyush/archive/2013/03/12/2956429.html

總結(jié)

以上是生活随笔為你收集整理的ZOJ-2770 Burn the Linked Camp 差分约束的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。