关闭

财富坊cff888: 差分约束系统的学习 poj1364(bellman和spfa)

标签: 差分约束系统
1755人阅读 评论(2) 收藏 举报
分类:

差分约束系统

【概念】:对于一个序列。

给出m个不等式,形如a+b<=k

问,同时满足这m个不等式的解存不存在。

推荐讲解:http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

【学习】:

我是通过一个三角不等式看懂的。

如下三个不等式:(摘自上述博客
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所示。
图三-2-1
      我们发现min{b, a+c}正好对应了A到C的最短路,而这三个不等式就是著名的三角不等式。将三个不等式推广到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
0

Sample 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");
	} 
}


0
0
查看评论

1275 Cashier Employment 差分约束系统+BELLMAN

<br />Cashier EmploymentTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 3409 Accepted: 1211<br />DescriptionA supermar...
  • hqd_acm
  • hqd_acm
  • 2010-08-12 16:32
  • 484

四、最短路径之Bellman-Ford与SPFA

1.简介           针对图中的最短路径计算,Dijkstra基本可以解决大部分问题,但是当图中有负权边出现的时候,该算法不再适用。为了解决该问题,提出了Bellman-Ford算法,适用范围是上去了,但是其复杂度为O(mn),其中m为图边...
  • moodytong
  • moodytong
  • 2012-06-14 22:21
  • 1476

Dijkstra、Bellman-Ford及Spfa算法思想对比

Dijkstradijkstra算法本质上算是贪心的思想,每次在剩余节点中找到离起点最近的节点放到队列中,并用来更新剩下的节点的距离,再将它标记上表示已经找到到它的最短路径,以后不用更新它了。这样做的原因是到一个节点的最短路径必然会经过比它离起点更近的节点,而如果一个节点的当前距离值比任何剩余节点都...
  • mmy1996
  • mmy1996
  • 2016-08-16 23:10
  • 5737

SPFA——基于Bellman-Ford的队列优化

Bellman-Ford算法在每一次实施松弛操作时,就会有一些顶点已经求得最短路径,此后这些顶点的最短路径的估计值就会一直保持不变,不再受后续松弛操作的影响,但是每次还要判断是否需要松弛,这里浪费了大量的时间. SPFA(Shortest Path Faster Algorithm)是基于Bell...
  • triumph92
  • triumph92
  • 2014-12-05 16:15
  • 823

UVA 11478 Halum(差分约束系统+Bellman-Ford)

?? 题意:给定一个有向图,每条边都有一个权值。每次你可以选择一个结点v和一个整数d,把所有以v为终点的边的权值减小d,把所有以v为起点的边的权值增加d,最后让所有边的权值的最小值大于零且尽量大。 ps:lrj的书上有个坑,说上说非负,其实原题说要大于0.....wa了好几发 分析:因为不同的...
  • u014664226
  • u014664226
  • 2015-07-26 01:58
  • 736

POJ 3169 Layout (差分约束系统,Bellman-Ford)

题目链接:http://poj.org/problem?id=3169 输入: 4 2 1 1 3 10 2 4 20 2 3 3 输出: 27 题意:第一行N头牛, 编号1 - N排成一列, 然后ML, MD。然后接下来ML行每行AL,BL,CL表示牛AL...
  • Strokess
  • Strokess
  • 2016-08-02 20:08
  • 203

POJ 1364 King【差分约束+SPFA/Bellman-Ford】

King Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 11846   Accepted: 4325 Description...
  • mengxiang000000
  • mengxiang000000
  • 2016-06-01 16:51
  • 500

最短路知识点总结(Dijkstra,Floyd,SPFA,Bellman-Ford)

最短路知识点总结(Dijkstra,Floyd,SPFA,Bellman-Ford) Dijkstra算法: 解决的问题:     带权重的有向图上单源最短路径问题。且权重都为非负值。如果采用的实现方法合适,Dijkstra运行时间要低于Bellman-Fo...
  • qq_33406883
  • qq_33406883
  • 2016-07-20 17:55
  • 1461

Bellman-Ford算法及其队列优化(SPFA)

一、算法概述         Bellman-Ford算法解决的是一般情况下的单源最短路径问题。所谓单源最短路径问题:给定一个图G=(V,E),我们希望找到从给定源结点s属于V到每个结点v属于V的最短路径。单源最短路径问题可以用来...
  • Insert_day
  • Insert_day
  • 2013-08-27 15:03
  • 1140

POJ 2983 Is the Information Reliable?(差分约束+SPFA+超级源点)

题意: 两个帝国打仗了,B帝国的南北线上有n个防御站,帝国A大概知道帝国B的布防情况,但是不一定对,给出两种他们之间的位置关系的信息要你判断是否存在这样一种布置关系。两种关系如下: P A B X 表示A在B北边X光年的位置。 V A B 表示A在B北...
  • Start_to_crazy
  • Start_to_crazy
  • 2017-11-26 20:01
  • 70
    个人资料
    • 访问:102707次
    • 积分:3008
    • 等级:
    • 排名:第13799名
    • 原创:197篇
    • 转载:9篇
    • 译文:0篇
    • 评论:33条
    博客专栏
    最新评论