想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
转载请注明出处:http://blog.csdn.net/wangjian8006
题目大意:现在假设有一个这样的序列,S={a1,a2,a3,a4...ai...at}
其中ai=a*si,其实这句可以忽略不看
现在给出一个不等式,使得ai+a(i+1)+a(i+2)+...+a(i+n)<ki或者是ai+a(i+1)+a(i+2)+...+a(i+n)>ki
首先给出两个数分别代表S序列有多少个,有多少个不等式
不等式可以这样描述
给出四个参数第一个数i可以代表序列的第几项,然后给出n,这样前面两个数就可以描述为ai+a(i+1)+...a(i+n),即从i到n的连续和,再给出一个符号和一个ki
当符号为gt代表‘>’,符号为lt代表‘<'
那么样例可以表示
1 2 gt 0
a1+a2+a3>0
2 2 lt 2
a2+a3+a4<2
最后问你所有不等式是否都满足条件,若满足输出lamentable kingdom,不满足输出successful conspiracy,这里要注意了,不要搞反了
解题思路:一个典型的差分约束,很容易推出约束不等式
首先设Si=a1+a2+a3+...+ai
那么根据样例可以得出
S3-S0>0---->S0-S3<=-1
S4-S1<2---->S4-S1<=1
因为差分约束的条件是小于等于,所以我们将ki-1可以得到一个等于号
那么通式可以表示为
a b gt c
S[a-1]-s[a+b]<=-ki-1
a b lt c
S[a+b]-S[a-1]<=ki-1
那么根据差分约束建图,加入这些有向边
gt: <a+b,a-1>=-ki-1
lt: <a-1,a+b>=ki-1
再根据bellman_ford判断是否有无负环即可
若出现负环了则这个序列不满足所有的不等式
/* Memory 168K Time 0MS */ #include <iostream> using namespace std; #define MAXE 110 #define MAXV 110 typedef struct{ int s,t,w; }Edge; Edge edge[MAXE]; int n,m,d[MAXV]; int bellman_ford(){ int i,j; memset(d,0,sizeof(d)); for(i=1;i<=n;i++){ for(j=0;j<m;j++){ if(d[edge[j].s]+edge[j].w<d[edge[j].t]){ d[edge[j].t]=d[edge[j].s]+edge[j].w; } } } for(j=0;j<m;j++) if(d[edge[j].s]+edge[j].w<d[edge[j].t]) return 0; return 1; } int main(){ int i,a,b,c; char s[3]; while(scanf("%d",&n) && n){ scanf("%d",&m); for(i=0;i<m;i++){ scanf("%d%d%s%d",&a,&b,s,&c); if(s[0]=='g'){ edge[i].s=b+a; edge[i].t=a-1; edge[i].w=-c-1; }else{ edge[i].s=a-1; edge[i].t=b+a; edge[i].w=c-1; } } if(!bellman_ford()) printf("successful conspiracy\n"); else printf("lamentable kingdom\n"); } return 0; }