首页 > 代码库 > zoj1260 king
zoj1260 king
题目描述：
从前有一个王国，皇后怀孕了。她祈祷到：如果我的孩子是儿子，我希望他是一个健康的国王。 9 个月后，她的孩子出生了，的确，她生了一个漂亮的儿子。但不幸的是，正如皇室家庭经常发生的那样，皇后的儿子智力迟钝。经过多年的学习后，他只能做整数的加法，以及比较加法的结果比给定的一个整数是大还是小。另外，用来求和的数必须排列成一个序列，他只能对序列中连续的整数进行求和。老国王对他的儿子非常不满意。但他决定为他的儿子准备一切，使得在他去世后，他的儿子
还能统治王国。考虑到他儿子的能力，他规定国王需要决断的所有问题必须表示成有限的整数序列，并且国王需要决断的问题只是判断这个序列的和与给定的一个约束的大小关系。作了这样的规定，至少还有一些希望：他的儿子能做出一些决策。老国王去世后，新国王开始统治王国。但很快，人们开始不满意他的决策，决定废除他。人们试图通过证明新国王的决策是错误的，从而名正言顺地废除新国王。因此，试图篡位的人们给新国王出了一些题目，让国王做出决策。问题是从序列 S = {a1, a2, ...,an}中取出一个子序列 Si = {aSi, aSi+1, ..., aSi+ni}。国王有一分钟的思考时间， 然后必须做出判断：他对每个子序列 Si 中的整数进行求和，即 aSi + aSi+1 + ... + aSi+ni，然后对每个子序列的和设定一个约束 ki，即 aSi + aSi+1 + ... + aSi+ni < ki，或 aSi + aSi+1 + ... + aSi+ni > ki。过了一会，他意识到他的判断是错误的。他不能取消他设定的约束，但他努力挽救自己：通过伪造篡位者给他的整数序列。他命令他的幕僚找出这样的一个序列 S，满足他设定的这些约束。请帮助幕僚，编写程序，判断这样的序列是否存在。
输入描述：
输入文件中包含多块输入。除最后一块输入外，每块输入对应一组问题及国王的决策。每块输入的第 1 行为两个整数： n 和 m，其中 0<n≤100 表示序列 S 的长度， 0<m≤100 为子序列 Si的个数。接下来有 m 行为国王的决策，每个决策的格式为： si, ni, oi, ki，其中 oi 代表关系运算符">"（用"gt"表示）、或"<"（用"lt"表示）， si、 ni 和 ki 的含义如题目描述中所述。最后一块输入只有一行，为 0，表示输入结束。
输出描述：
对输入文件中的每块输入，输出占一行字符串：当满足约束的序列 S 不存在时，输出"successful conspiracy"；否则输出"lamentable kingdom"。对最后一块输入，没有输出内容。
样例输入：
4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0
样例输出：
lamentable kingdom
successful conspiracy
______________________________________________________
又是一道差分约束，大同小异，唯一与前面不同之处在于需要给他认为提供一个源点，从而计算其他点的最短距离，判断是否会有负环。
_______________________________________________________
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 7 using namespace std; 8 const int maxm=305; 9 int n,m; 10 struct edge 11 { 12 int u,v,w,next; 13 }e[maxm]; 14 int head[106],js; 15 void init() 16 { 17 memset(head,0,sizeof(head)); 18 js=0; 19 } 20 void addage(int u,int v,int w) 21 { 22 e[++js].u=u;e[js].v=v;e[js].w=w; 23 e[js].next=head[u];head[u]=js; 24 } 25 queue<int>q; 26 int dis[105]; 27 bool inq[105]; 28 int inqt[105]; 29 bool spfa() 30 { 31 memset(inq,0,sizeof(inq)); 32 memset(inqt,0,sizeof(inqt)); 33 memset(dis,0x7f,sizeof(dis)); 34 dis[105]=0; 35 inq[105]=1; 36 inqt[105]=1; 37 q.push(105); 38 while(!q.empty()) 39 { 40 int u=q.front(); 41 q.pop(); 42 inq[u]=0; 43 for(int i=head[u];i;i=e[i].next) 44 { 45 int v=e[i].v; 46 if(dis[v]>dis[u]+e[i].w) 47 { 48 dis[v]=dis[u]+e[i].w; 49 if(!inq[v]) 50 { 51 q.push(v); 52 inq[v]=1; 53 inqt[v]++; 54 if(inqt[v]>101) 55 return 0; 56 } 57 } 58 } 59 } 60 return 1; 61 } 62 int main() 63 { 64 while(scanf("%d%d",&n,&m)==2) 65 { 66 init(); 67 int si,ni,ki; 68 char oi[5]; 69 for(int i=0;i<m;i++) 70 { 71 scanf("%d%d%s%d",&si,&ni,oi,&ki); 72 if(oi[0]==‘g‘) 73 { 74 addage(si+ni,si-1,-ki-1); 75 addage(105,si+ni,0); 76 addage(105,si-1,0); 77 } 78 else 79 { 80 addage(si-1,si+ni,ki-1); 81 addage(105,si+ni,0); 82 addage(105,si-1,0); 83 } 84 } 85 if(spfa())printf("lamentable kingdom\n"); 86 else printf("successful conspiracy\n"); 87 } 88 return 0; 89 }
zoj1260 king