Better man

改变性格 改变命运!

 

差分约束系统(zoj1508)

给出一组限制条件 a[i] - a[j] ≥ k 或 a[i] - a[j] ≤ k。
要你求出a[t] - a[s]的最小值或最大值。

先举一个题目的例子:poj1201.
题目大意是,有一个集合S。已知其满足以下一些条件:
对于给出的n组 a[i] b[i] c[i],有从a[i]~b[i]这连续的k个整数中,至少有c[i]个在集合S内。求S最少的元素个数。

这个题目转化为我们的差分约束系统如下:
如果i∈S,则t[i]=1,否则t[i]=0。另s[i] = ∑t[j] (j = 0 ~ i),这样子,题目的条件就可以用下面的式子表示:
s[b[i]] - s[a[i]-1] ≥ c[i]
s[i] - s[i+1] ≥ -1
s[i+1] - s[i] ≥ 0
注意后面两个式子是s先天的性质。
我们要求的就是s[n] - s[-1]的最小值(因为题目都是非负的嘛)。

然后我们介绍解决差分约束问题的方法:Bellman-Ford算法,是不是很神奇呢?没错,差分约束系统可以通过转换成图论最短路问题来解决:
注意到最短路算法的松弛操作:if (d[j] > d[i] + w[i][j]) d[j] = d[i] + w[i][j]。
这其中的三角形不等式:d[j] ≤ d[i] + w[i][j]简单变形就成了d[i] - d[j] >= -w[i][j]。这样就图形的最短路就维护了一个不等式组。所以,我们可以建立一个图:对于每一个不等式s[i] - s[j] >= c,就从j连一条指向i的边,其中边的权值c,这样求一个最长路,就是d[n] - d[-1]就是s[n] - s[-1]的最小值了,且对应的方案就是s[i] = d[i]。

有的同学要问了:无解怎么办啊?很简单,你将会发现Bellman-Ford算法如果找出了”负权回路”,那么该系统无解。只要系统无解,就必然存在”负权圈”。
那么如果求s[n] - s[-1]的最小值呢?其实和上面的方法类似了,大家可以自己推导一下。而且有很多问题仅仅要你给出是否有解的判断,那就不要想那么多了。

实际上是求最长路,其实就是把松弛操作的符号改变即可

其实此题可以用spfa实现,效率很高

开始做此题时

连续超时很久

此题每次要进行三次松弛操作

 1 for(int j=Min;j<Max;++j)
 2 {
 3       if(d[j]!=INT_MIN&&d[j]>d[j+1])
 4       {
 5             d[j+1]=d[j];
 6             update=0;
 7       }
 8 }
 9 for(int j=Max;j>Min;--j)
10 {
11       if(d[j]!=INT_MIN&&d[j]-1>d[j-1])
12       {
13             update=0;
14             d[j-1]=d[j]-1;
15       }
16 }
一开始将两个松弛操作合并到一起进行

超时

第二次分开

仍然超时

第三次

改变松弛的顺序

即第三个松弛从上到下(之前是从下到上)

这样做的目的就是避免了重复的松弛操作!

 1 #include <iostream>
 2 using namespace std;
 3 struct Edge
 4 {
 5       int x,y,d;
 6 }edge[50000+5];
 7 int n;
 8 int d[50000+5];
 9 int main()
10 {      
11      while(scanf("%d",&n)!=EOF)
12      {
13             int Min=INT_MAX;
14             int Max=INT_MIN;
15             for(int i=0;i<n;++i)
16             {
17                   scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].d);
18                   if(--edge[i].x<Min)Min=edge[i].x;
19                   if(edge[i].y>Max)Max=edge[i].y;
20             }
21             int tmp=Max-Min+1;
22             for(int i=Min;i<=Max;++i)
23                   d[i]=INT_MIN;
24             d[Min]=0;
25             for(int i=0;i<tmp;++i)
26             {
27                   bool update=1;
28                   for(int j=0;j<n;++j)
29                   {
30                         if(d[edge[j].x]!=INT_MIN&&d[edge[j].y]<d[edge[j].x]+edge[j].d) 
31                         {
32                               update=0;
33                               d[edge[j].y]=d[edge[j].x]+edge[j].d;
34                         }
35                   }
36                   for(int j=Min;j<Max;++j)
37                   {
38                         if(d[j]!=INT_MIN&&d[j]>d[j+1])
39                         {
40                               d[j+1]=d[j];
41                               update=0;
42                         }
43                     }
44                   for(int j=Max;j>Min;--j)
45                   {
46                         if(d[j]!=INT_MIN&&d[j]-1>d[j-1])
47                         {
48                               update=0;
49                               d[j-1]=d[j]-1;
50                         }
51                   }
52                   if(update)break;
53             }
54             printf("%d\n",d[Max]-d[Min]);
55       }
56       return 0;
57 }

posted on 2009-02-05 11:32 SHFACM 阅读(1414) 评论(1)  编辑 收藏 引用

评论

# re: 差分约束系统(zoj1508)[未登录] 2011-02-19 11:16 lj

终于看懂些了!多谢楼主!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(2)

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜