两张图片足矣说明问题。
任何形如上述约束条件的取值问题均可转化为差分约束问题。
重点:约束图的建立。
在Ax<=B的系统中,将m*n的线性规划矩阵A看做是n个结点和m条边的图的邻接矩阵。上图中,每个节点的值是delta(v0,vi),也就是v0到vi的最短路的值。
详细来说:G(V,E),是一个带权重的有向图,其中
V={v0,v1,v2,...,vn};
E={(vi,vj):xj-xi<=bk}U{(v0,v1),(v0,v2),...(v0,vn)}.
那么,
1.图中自然就包含一个v0,用于保证图中至少含有一个点(下面代码的超级源点)。
2.边集E包含的是每个差分约束的边,再加上边(v0,vi),i=1,2,3,...,n。如果xj-xi<=bk是一个差分约束条件,则边(vi,vj)的权重是bk.所有从v0出发的边权重是0。
该题:
所谓 P A B X 可以转换为
A-B>=x && A-B<=X <=> B-A <= -X && A-B <=X
而 V A B <=> A>=B+1 <=> B + 1 <=A <=> B - A <= -1。
然后套spfa即可了。
#include <iostream> #include <algorithm> #include <vector> #include <queue> #define MAXN 2000 #define MAX 999999999 using namespace std; int n, m; struct Tnode { int id, len; Tnode(int a, int b) : id(a), len(b) {} }; vector <Tnode> adj[MAXN]; int dis[MAXN], vis[MAXN]; bool hashtable[MAXN]; queue <int> q; bool spfa() { memset(hashtable, false, sizeof(hashtable)); memset(vis, 0, sizeof(vis)); dis[0] = 0; while (!q.empty()) q.pop(); q.push(0); while (!q.empty()) { int now = q.front(); q.pop(); hashtable[now] = false; for (int i = 0; i < adj[now].size(); i++) { int v = adj[now][i].id; int cost = adj[now][i].len; if (dis[v] > dis[now] + cost) { dis[v] = dis[now] + cost; if (!hashtable[v]) { q.push(v); hashtable[v] = true; } if (++vis[v] >= n) return false; } } } return true; } int main() { while (cin>>n>>m) { for (int i = 0; i <= n; i++) { adj[i].clear(); dis[i] = MAX; } int a, b, c; char ch; for (int i = 0; i < m; i++) { cin>>ch; if (ch == ‘P‘) { cin>>a>>b>>c; adj[b].push_back(Tnode(a, c)); adj[a].push_back(Tnode(b, -c)); } else { cin>>a>>b; adj[a].push_back(Tnode(b, -1)); } } for (int i = 0; i <= n; i++) adj[0].push_back(Tnode(i, 0)); if (!spfa()) cout << "Unreliable" << endl; else cout << "Reliable" << endl; } }
原文:http://blog.csdn.net/zhengnanlee/article/details/19960685