差分约束专题
先摘抄一段：
如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
求解差分约束系统，可以转化成图论的单源最短路径问题。观察xj-xi<=bk，会发现它类似最短路中的三角不等式d[v]<=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。因此，以每个变量xi为结点，对于约束条件xj-xi<=bk，连接一条边(i,j)，边权为bk。我们再增加一个源点s,s与所有定点相连，边权均为0。对这个图，以s为源点运行Bellman-ford算法（或SPFA算法），最终{d[ i]}即为一组可行解。
#include<iostream>
#include <cstdio>
using namespace std;
struct Edge
{
int u,v,w;
}e[101];
int sum[101];
int M,N;
bool BellmanFord()
{
for(int i=0;i<=N;i++)
sum[i]=0;
for(int k=0;k<N;k++)
for(int i=0;i<M;i++)
if(sum[e[i].u]+e[i].w<sum[e[i].v])
sum[e[i].v]=sum[e[i].u]+e[i].w;
for(int i=0;i<M;i++)
if(sum[e[i].u]+e[i].w<sum[e[i].v])
return false;
return true;
}
int main()
{
while(scanf("%d",&N),N)
{
scanf("%d",&M);
char op[3];
int si,ni,ki;
for(int i=0;i<M;i++)
{
scanf("%d%d%s%d",&si,∋,op,&ki);
if(op[0]=='g')
{
e[i].u=si+ni;
e[i].v=si-1;
e[i].w=-ki-1;
}
else
{
e[i].u=si-1;
e[i].v=si+ni;
e[i].w=ki-1;
}
}
if(!BellmanFord())
printf("successful conspiracy\n");
else
printf("lamentable kingdom\n");
}
return 0;
}
poj 3169 Layout难度*
题意：农夫FJ的牛排成一行等着吃饭，有些牛相互讨厌，他们之间距离的至少大于di，有些牛相互暧昧，他们之间的距离最多小于li问满足条件的队伍的最长距离。
解析：应该是比较水的一个题了(第一次做多校一个类似的题时居然没看出来)。求最大值，用最短路。如果A与B相互讨厌，他们之间的距离应大于di，则有dis[B]-dis[A]>=di，建一条<B,A,-di>的边。暧昧时同理。spfa求最短路时出现负环说明无解，dis[N]=INF则说明牛的位置可以是任意的(因为没有限制条件传递到N,所以N的值是初始的值，即N的位置不受限制),否则输出dis[N]。(其实应该添加dis[i]>=dis[i-1]的，但没加也过了)
poj 2983 Is the Information Reliable?难度**
题意：跟上面一题是一样的，这题有两种输入：P A B X表示A到B的距离正好等于X，V A B表示A的距离至少比B大1。问满足条件的解是否存在。
解析：对于P A B X，即dis[A]-dis[B]=X可以转化为：X<=dis[A]-dis[B]<=X ，据此构出两条边。对于V A B 即dis[A]-dis[B]>=1，再构造出边。这题要小心了，很多人用BellmanFord过用SPFA Wa了，要注意有些点是孤立点，或者一些集合构成孤立的集合，所以我们要建一个超级源点，连到所有的点，边的w=0 。最后判负环即可。
zoj 1455 Schedule Problem难度***
题意：一个工程分为N个部分，给出每个部分持续时间，以及几对部分之间的关系：FAS, FAF, SAF and SAS.输出每个部分的起始时间。
解析：约束关系比较明朗,以t[i]表示部分i什么时候开始d[i]表示部分i的持续时间，则有：
FAS: t[a]>=t[b]+d[a]
FAF: t[a]>=t[b]+d[b]-d[a]
SAS: t[a]>=t[b]
SAF: t[a]>=t[b]+d[b]
求最长路，设一个超级源点到所有点的权值为0.最后输出t[i]即可。