POJ - 1364
题目大意:现在假设有一个这样的序列，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判断是否有无负环即可
若出现负环了则这个序列不满足所有的不等式
/* 写了队列版的spfa，不知道为什么dfs版的不行 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn=21000; int n,m,head[maxn*2],num,dis[maxn],step[maxn]; bool vis[maxn]; char ch[5]; struct node{ int to,pre,v; }e[maxn*2]; void Insert(int from,int to,int v){ e[++num].to=to; e[num].v=v; e[num].pre=head[from]; head[from]=num; } bool spfa(){ queue<int>q; for(int i=1;i<=n;i++){ vis[i]=1; q.push(i); } vis[1]=1; dis[1]=0; step[1]=1; while(!q.empty()){ int point=q.front();q.pop(); vis[point]=0; for(int i=head[point];i;i=e[i].pre){ int to=e[i].to; if(dis[to]>dis[point]+e[i].v){ dis[to]=dis[point]+e[i].v; if(!vis[to]){ step[to]++; q.push(to); if(step[to]>n) return 1; } } } } return 0; } int main(){ while(1){ scanf("%d",&n); if(n==0)return 0; scanf("%d",&m); num=0; memset(head,0,sizeof(head)); memset(dis,127/3,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(step,0,sizeof(step)); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%s%d",&x,&y,ch,&z); if(ch[0]=='g')//> Insert(x+y,x-1,-z-1); if(ch[0]=='l')//< Insert(x-1,x+y,z-1); } if(spfa())printf("successful conspiracy "); else printf("lamentable kingdom "); } return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn=21000; int n,m,head[maxn*2],num,dis[maxn],step[maxn]; bool vis[maxn],flag; char ch[5]; struct node{ int to,pre,v; }e[maxn*2]; void Insert(int from,int to,int v){ e[++num].to=to; e[num].v=v; e[num].pre=head[from]; head[from]=num; } void spfa(int now){ if(flag)return; vis[now]=1; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(dis[to]>dis[now]+e[i].v){ dis[to]=dis[now]+e[i].v; if(vis[to]){ flag=1; return;//有负环 } else spfa(to); } } vis[now]=0; } int main(){ while(1){ scanf("%d",&n); if(n==0)return 0; scanf("%d",&m); num=0; memset(head,0,sizeof(head)); memset(dis,127/3,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(step,0,sizeof(step)); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%s%d",&x,&y,ch,&z); if(ch[0]=='g')//> Insert(x+y,x-1,-z-1); if(ch[0]=='l')//< Insert(x-1,x+y,z-1); } flag=0; for(int i=1;i<=n;i++){ Insert(0,i,0); } spfa(0); if(flag)printf("successful conspiracy "); else printf("lamentable kingdom "); } return 0; }