差分約束系統(tǒng)
在一個差分約束系統(tǒng)(system of difference constraints)中，線性規(guī)劃矩陣A的每一行包含一個1和一個-1，A的其他所有元素都為0。因此，由Ax≤b給出的約束條件是m個差分約束集合，其中包含n個未知量，對應(yīng)的線性規(guī)劃矩陣A為m行n列。每個約束條件為如下形式的簡單線性不等式：xj-xi≤bk。其中1≤i,j≤n，1≤k≤m。
例如，考慮這樣一個問題，尋找一個5維向量x=(xi)以滿足：
這一問題等價于找出未知量xi，i=1,2,…,5，滿足下列8個差分約束條件：
x1-x2≤0
x1-x5≤-1
x2-x5≤1
x3-x1≤5
x4-x1≤4
x4-x3≤-1
x5-x3≤-3
x5-x4≤-3
該問題的一個解為x=(-5,-3,0,-1,-4)，另一個解y=(0,2,5,4,1)，這2個解是有聯(lián)系的：y中的每個元素比x中相應(yīng)的元素大5。
引理：設(shè)x=(x1,x2,…,xn)是差分約束系統(tǒng)Ax≤b的一個解，d為任意常數(shù)。則x+d=(x1+d,x2+d,…,xn+d)也是該系統(tǒng)Ax≤b的一個解。
約束圖
在一個差分約束系統(tǒng)Ax≤b中，m X n的線性規(guī)劃矩陣A可被看做是n頂點，m條邊的圖的關(guān)聯(lián)矩陣。對于i=1,2,…,n，圖中的每一個頂點vi對應(yīng)著n個未知量的一個xi。圖中的每個有向邊對應(yīng)著關(guān)于兩個未知量的m個不等式中的一個。
給定一個差分約束系統(tǒng)Ax≤b，相應(yīng)的約束圖是一個帶權(quán)有向圖G=(V,E)，其中V={v0,v1,…,vn}，而且E={ (vi,vj) : xj-xi≤bk是一個約束}∪{ (v0,v1) , (v0,v2) , … , (v0,vn) }。引入附加頂點v0是為了保證其他每個頂點均從v0可達(dá)。因此，頂點集合V由對應(yīng)于每個未知量xi的頂點vi和附加的頂點v0組成。邊的集合E由對應(yīng)于每個差分約束條件的邊與對應(yīng)于每個未知量xi的邊(v0,vi)構(gòu)成。如果xj-xi≤bk是一個差分約束，則邊(vi,vj)的權(quán)w(vi,vj)=bk（注意i和j不能顛倒），從v0出發(fā)的每條邊的權(quán)值均為0。
定理：給定一差分約束系統(tǒng)Ax≤b，設(shè)G=(V,E)為其相應(yīng)的約束圖。如果G不包含負(fù)權(quán)回路，那么x=( d(v0,v1) , d(v0,v2) , … , d(v0,vn) )是此系統(tǒng)的一可行解，其中d(v0,vi)是約束圖中v0到vi的最短路徑(i=1,2,…,n)。如果G包含負(fù)權(quán)回路，那么此系統(tǒng)不存在可行解。
差分約束問題的求解
由上述定理可知，可以采用Bellman-Ford算法對差分約束問題求解。因為在約束圖中，從源點v0到其他所有頂點間均存在邊，因此約束圖中任何負(fù)權(quán)回路均從v0可達(dá)。如果Bellman-Ford算法返回TRUE，則最短路徑權(quán)給出了此系統(tǒng)的一個可行解；如果返回FALSE，則差分約束系統(tǒng)無可行解。
關(guān)于n個未知量m個約束條件的一個差分約束系統(tǒng)產(chǎn)生出一個具有n+1個頂點和n+m條邊的約束圖。因此采用Bellman-Ford算法，可以再O((n+1)(n+m))=O(n^2+nm)時間內(nèi)將系統(tǒng)解決。此外，可以用SPFA算法進(jìn)行優(yōu)化，復(fù)雜度為O(km)，其中k 為常數(shù)。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1364
Description
Once, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: ``If my child was a son and if only he was a sound king.'' After nine months her child was born, and indeed, she gave birth to a nice son.
Unfortunately, as it used to happen in royal families, the son was a little retarded. After many years of study he was able just to add integer numbers and to compare whether the result is greater or less than a given integer number. In addition, the numbers had to be written in a sequence and he was able to sum just continuous subsequences of the sequence.
The old king was very unhappy of his son. But he was ready to make everything to enable his son to govern the kingdom after his death. With regards to his son's skills he decided that every problem the king had to decide about had to be presented in a form of a finite sequence of integer numbers and the decision about it would be done by stating an integer constraint (i.e. an upper or lower limit) for the sum of that sequence. In this way there was at least some hope that his son would be able to make some decisions.
After the old king died, the young king began to reign. But very soon, a lot of people became very unsatisfied with his decisions and decided to dethrone him. They tried to do it by proving that his decisions were wrong.
Therefore some conspirators presented to the young king a set of problems that he had to decide about. The set of problems was in the form of subsequences Si = {aSi, aSi+1, ..., aSi+ni} of a sequence S = {a1, a2, ..., an}. The king thought a minute and then decided, i.e. he set for the sum aSi + aSi+1 + ... + aSi+ni of each subsequence Si an integer constraint ki (i.e. aSi + aSi+1 + ... + aSi+ni < ki or aSi + aSi+1 + ... + aSi+ni > ki resp.) and declared these constraints as his decisions.
After a while he realized that some of his decisions were wrong. He could not revoke the declared constraints but trying to save himself he decided to fake the sequence that he was given. He ordered to his advisors to find such a sequence S that would satisfy the constraints he set. Help the advisors of the king and write a program that decides whether such a sequence exists or not.
Input
The input consists of blocks of lines. Each block except the last corresponds to one set of problems and king's decisions about them. In the first line of the block there are integers n, and m where 0 < n <= 100 is length of the sequence S and 0 < m <= 100 is the number of subsequences Si. Next m lines contain particular decisions coded in the form of quadruples si, ni, oi, ki, where oi represents operator > (coded as gt) or operator < (coded as lt) respectively. The symbols si, ni and ki have the meaning described above. The last block consists of just one line containing 0.
Output
The output contains the lines corresponding to the blocks in the input. A line contains text successful conspiracy when such a sequence does not exist. Otherwise it contains text lamentable kingdom. There is no line in the output corresponding to the last ``null'' block of the input.
Sample Input
4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0
Sample Output
lamentable kingdom
successful conspiracy
Source
很典型的差分約束，關(guān)鍵在于怎么構(gòu)圖。
這里我們設(shè)Sum(i) = A1 + A2 + … + Ai-1
那么輸入的si ni oi ki
就可以轉(zhuǎn)換成如下的約束式：Sum(si+ni+1) - Sum(si) oi ki
#include <iostream>
using namespace std;
const int MAXN = 120;
const int inf = 0x7f;
struct node
{
int s,e,v;
}edge[MAXN];
int n,m,d[MAXN];
bool bellman_ford(){
int i,j;
for(i=0;i<=n+1;i++) d[i]=inf;
for(d[0]=0,i=1;i<=n+1;i++)
for(j=0;j<=(n+m);j++)
if(d[edge[j].s]+edge[j].v<d[edge[j].e])
d[edge[j].e]=d[edge[j].s]+edge[j].v;
for(i=0;i<=(n+m);i++)
if(d[edge[i].s]+edge[i].v<d[edge[i].e])
return false;
return true;
}
int main(){
char oi[5];
int si,ni,k,i,j;
while(scanf("%d",&n),n){
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%d %d\n",&si,&ni);
scanf("%s %d",oi,&k);
if(oi[0]=='g')
edge[i].s=si,edge[i].e=si+ni+1,edge[i].v=-k-1;
else
edge[i].s=si+ni+1,edge[i].e=si,edge[i].v=k-1;
}
for(i=1,j=m;i<=n+1;i++,j++)
edge[j].s=0,edge[j].e=i,edge[j].v=0;
puts(bellman_ford()?"lamentable kingdom":"successful conspiracy");
}
return 0;
}