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.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
題目很長，意思是：有一個長度為n的序列和它的m個子序列。每一個子序列的和都有一個k來約束。gt代表大於k，lt代表小於k。問是否存在這個長度為n的序列。
讓我們來思考這道題，首先對於給出的每個子序列我們可以看成子序列尾部到原序列起點的和減去子序列起點前一位到原序列起點的和。
例如：原序列為a[1]+a[2]+.....a[s]+...a[n]+a[n+1]+...... 子序列a[s]+....+a[n]=S[n]-S[s-1];
這樣我們可以把S[n], S[s-1]看成兩點，約束值k就可以看成對這兩點間權大小和方向的約束。 按照上述過程可以建立起表示S[]點間關系的圖。則就把問題轉化為了最短路徑問題。
若這個序列存在，則S[i]到圖中任意一點都有最短路徑，則圖中不存在負環。所以判斷是否存在序列就是判斷是否存在負環。
好，具體思路清楚了，我們來研究如何建立起圖。題中給出的約束條件有 > 和 < 。我們要做的事是將所有的約束條件全部轉化為<= 。 即建立差分約束系統。
分析:
我們令S[i]= a1+a2+..+ai. 所以對於每一條約束條件比如:
a[si]+a[si+1]+…+a[si+ni]< ki . 我們可以轉化為 S[si+ni] – S[si-1] <= ki-1.
這樣就可以轉化為了差分約束系統了.
該系統具有點的集合為0, 1,… n.其中對於S[si+ni] – S[si-1] <= ki-1條件我們可以得到 si-1 到 si+ni 的權值為ki-1的邊.
對於a[si]+a[si+1]+…+a[si+ni] >ki 即 S[si+ni] – S[si-1] >=ki+1 我們可以得到 si+ni 到 si-1 的權值為-ki-1 的邊.
而在判斷差分約束系統是否有解時，建立的路徑圖可能不是連通的。因此我們還需要虛構一個超級源n+1號點.使得從n+1號點有邊出來到0,1,…n號點且權值為0.
注意：圖中原有的點是0到n共n+1個點
第一次討論差分約束系統問題，若敘述有誤，請各位指出。
具體代碼如下：
#include#include #include #define maxn 110 #define maxm 10010 #define INF 0x3f3f3f using namespace std; int dis[maxn],visit[maxn],head[maxn],top,n; struct node { int to,val,next; }edge[maxm]; void add(int a,int b,int c) { edge[top].to=b; edge[top].val=c; edge[top].next=head[a]; head[a]=top++; } void spfa() { int i,u,v,mark[maxn]; queue q; for(i=0;i<=n+1;++i) { dis[i]=INF; visit[i]=0; mark[i]=0; } dis[n+1]=0; q.push(n+1);//n+1為虛擬的超級源點 visit[n+1]=1; mark[n+1]++; while(!q.empty()) { u=q.front(); q.pop(); visit[u]=0; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].to; if(dis[v]>dis[u]+edge[i].val) { dis[v]=dis[u]+edge[i].val; if(!visit[v]) { q.push(v); visit[v]=1; mark[v]++; if(mark[v]>n+1)//不包括超級源點 { printf(successful conspiracy ); return ; } } } } } printf(lamentable kingdom ); } int main() { int m,s,len,k,i; char c[3]; while(scanf(%d,&n)&&n) { scanf(%d,&m); top=0; memset(head,-1,sizeof(head)); while(m--) { scanf(%d%d%s%d,&s,&len,c,&k); if(c[0]=='g') add(s+len,s-1,-(k+1));//此處有疑問見代碼前面的分析 if(c[0]=='l') add(s-1,s+len,k-1); } for(i=0;i<=n;++i)//連接超級源點與其他點，邊權為0 add(n+1,i,0); spfa(); } return 0; }
