先摘抄一段：

　　如果一个系统由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的牛排成一行等着吃饭，有些牛相互讨厌，他们之间距离的至少大于d_i，有些牛相互暧昧，他们之间的距离最多小于l_i问满足条件的队伍的最长距离。

解析：应该是比较水的一个题了(第一次做多校一个类似的题时居然没看出来)。求最大值，用最短路。如果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]即可。

• 相关文章