差分约束系统
【概念】：对于一个序列。
给出m个不等式，形如a+b<=k
问，同时满足这m个不等式的解存不存在。
【学习】：
我是通过一个三角不等式看懂的。
如下三个不等式：（摘自上述博客）
B - A <= c (1)
C - B <= a (2)
C - A <= b (3)
我们想要知道C - A的最大值，通过(1) + (2)，可以得到 C - A <= a + c，所以这个问题其实就是求min{b, a+c}。 将上面的三个不等式按照 三-1 数形结合
图三-2-1
三角不等式。将三个不等式推广到m个，变量推广到n个，就变成了n个点m条边的最短路问题了。
不管题目给出的不等式是 > , < ,>=，我们都可以通过移项等操作统一为<=
然后可以用最短路的思想（结合这个三角不等式理解），对这m个不等式做一个收缩操作
即求一条最短路，比如求的0->n的最短路为len，恢复成X0 - Xn <= len；
这条最短路如果求得出来，那么这个序列就是存在的。
什么时候求不出来呢？
建成的有向图是存在负环的时候。这是因为有几个不等式是相互矛盾的，比方x-y>0和x-y<0。不可能同时成立
这时用bellman算法可以直接判环。
或者是spfa计算每个点的遍历次数，某个点的次数>n则存在负环
为什么存在负环？
比方x-y>5和x-y<3（相矛盾），统一一下符号就是：y-x<= -6 , x-y<=2
这样建图就是x->y=2，y->x=-6
很明显这是一个负环！也就是只要存在相矛盾的不等式，一定会构成负环，你找不出反例
当存在负环时，最短路算法计算过程中会不断将路长变小（因为负数越加越小，相当于减法）
所以用spfa或bellman判环就是核心。
【例题】poj1364
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 13843
Accepted: 4920
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
0Sample Output
lamentable kingdom
successful conspiracy【题意】：
问是否存在一个n元素的序列满足输入的不等式。但是这里比较的是子段和。
比如输入的第二行 2 2 lt 2 ，表示从第2项起，连续的2项之和 小于 2
【解析】：
将输入的不等式统一为<=的形式，并建有向图。然后判负环。
两种代码理论上都需要建一个超级源点，指向所有点，且权值为0。
理由：作为最短路起点，权值为0不影响判环
但是会在一次遍历过后使得所有的最短路均为0、
然后n次遍历后还会继续被更新缩小，只能说明存在负环，越负越小。
若不存在负环，dis数组始终为0
bellman写法中可以省略超级源点，直接将dis数组清为0即可。
那么如果存在负环，权值为0的最短路照样会被更新，而达到判环的目的（仅限判环，求最短路不能这么玩）
而在spfa中这个超级源点的作用也就仅仅是给spfa一个头结点作为bfs的开始。
一次遍历之后dis必然全为0。判环原理同bellman
总之所谓的判环，一定就是不断缩小最短路以至于无限缩小。只要在n次之后终结即可
【代码】bellman和spfa（后者效率高）
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node{
int u,to,len,next;
}e[10101];
int head[101];
int n,m,cnt;
int dis[102];
int in[102];//记录入度
void add(int u,int v,int len)
{
e[cnt]=(node){u,v,len,head[u]};
head[u]=cnt++;
}
int bellman()
{
memset(dis,0,sizeof(dis));
//收缩操作
for(int i=0;i<=n;i++)
for(int j=0;j<cnt;j++)
if(dis[e[j].to]>dis[e[j].u]+e[j].len)
dis[e[j].to]=dis[e[j].u]+e[j].len;
for(int j=0;j<cnt;j++)
if(dis[e[j].to]>dis[e[j].u]+e[j].len)
return 0;
return 1;
}
int main()
{
while(scanf("%d",&n),n)
{
scanf("%d",&m);
memset(in,0,sizeof(in));
memset(head,-1,sizeof(head));
cnt=0;
while(m--)
{
int u,len,k; char s[9];
scanf("%d%d%s%d",&u,&len,s,&k);//sum(au~au+len)
if(s[0]=='g')//>要转<=
add(u+len,u-1,-k-1);
else
add(u-1,u+len,k-1);
}
int ans=bellman();
if(ans)puts("lamentable kingdom");
else puts("successful conspiracy");
}
}#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node{
int u,to,len,next;
}e[10101];
int head[101];
int n,m,cnt;
int dis[102];
int in[102];//记录入度
void add(int u,int v,int len)
{
e[cnt]=(node){u,v,len,head[u]};
head[u]=cnt++;
}
int spfa(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(in,0,sizeof(in));
queue<int>q;
q.push(s);
dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]>dis[u]+e[i].len)
{
dis[v]=dis[u]+e[i].len;
q.push(v);
in[v]++;
if(in[v]>n+1)return 0;
}
}
}
return 1;
}
int main()
{
while(scanf("%d",&n),n)
{
scanf("%d",&m);
memset(in,0,sizeof(in));
memset(head,-1,sizeof(head));
cnt=0;
while(m--)
{
int u,len,k; char s[9];
scanf("%d%d%s%d",&u,&len,s,&k);//sum(au~au+len)
if(s[0]=='g')//>要转<=
add(u+len,u-1,-k-1);
else
add(u-1,u+len,k-1);
}
//建超级源点
for(int i=0;i<=n;i++)//注意前面建的图实际上有n+1个点
add(n+2,i,0);
int ans=spfa(n+2);
if(ans)puts("lamentable kingdom");
else puts("successful conspiracy");
}
}