浅谈 差分约束

发表于 | 分类于 | 阅读次数:
字数统计: 1,231 字

近期实验室专题学习讲到了差分约束系统，就写点东西来总结一下自己学到的东西吧。首先是一种的比较方便的图的存储方式——链式前向星，然后是在Dijkstra、Bellman-Ford之后的一种非常快的能够求出负环的最短路算法——SPFA，最后是一个最短路的变式——差分约束系统。

链式前向星

存储图我们通常有两种方法：一种是邻接矩阵法，这个是最基本的东西；另外一种是邻接链表法，通常使用vector的数组表示（相当于一个二维数组）。
首先我们要知道什么是前向星，前向星就是一个边的数组，用起点进行排序，起点相同的情况下用终点进行排序。这样我们就可以找到点所连得所有边了
链式前向星在以上的基础上避免了排序，用一个head数组来存储每个节点的第一条边，后面的边想要加入进来通过边的结构体中的next来实现，新加入进来的边成为第一条边，这样我们取出边的顺序与插入的顺序是相反的，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
strut Node
{
	int v,w,next;
};

void addedge(int u,int v,int w)
{
	edges[id].v=v;
	edges[id].w=w;
	edges[id].next=head[u];    //把之前的第一条边作为当前边的最后一条边
	head[u]=id++;
}

SPFA

SPFA就是在Bellman-Ford算法的基础上加一个队列优化，减少冗余的松弛操作。把进行完松弛操作的点加入队列中，同时在判断负边方面，SPFA也具有比较大的优势。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void spfa(int st)
{
    fill(visit,visit+maxn,0);
    fill(dist,dist+maxn,-INF);

    queue<int> Q;
    visit[st]=1;
    dist[st]=0;
    Q.push(st);
    while (!Q.empty())
    {
        int now=Q.front();
        Q.pop();

        visit[now]=0;
        for(int i=head[now];i!=-1;i=edges[i].next)
        {
            int v=edges[i].v;
            int w=edges[i].w;
            if(dist[v]<dist[now]+w)
            {
                dist[v]=dist[now]+w;
                if(!visit[v])
                {
                    Q.push(v);
                    visit[v]=1;
                }
            }
        }
    }
}

差分约束

我们把一个类似于 d[u]-d[v]<=w 的不等式组放到图中来，看成两个点u、v之间的的距离小于等于w，这样每一个方程组就可以看成图中的一条边，我们构建一个图。这样求(d[0]-d[n])的最大值这样的问题我们就可以放到图中用最短路来解决。

POJ 1201

题意

在一个区间0-50000内，给出n组约束条件，每一个条件表示在一个区间[a,b]内至少有c个点，让你求整个区间里面至少有的点数。

题解

  • 用一个数组d[i]表示从0到i的点数，这样区间[a,b]中至少含有的点数就可以表示为d[b]-d[a-1]，因为要减一处理，所以要多加一个数，不然0作为起点就不好表示。这样根据所给的条件就能够很多不等式组
  • 题目中还隐含一个条件，就是每个点最后只能最多含有一个点，即 1>=d[i+1]-d[i]>=0
  • 转化为最长路问题，通过SPFA来进行求解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

#define INF 0x3f3f3ff
const int maxn=500005;

struct Node
{
    int v,w,next;     //体现链式
}edges[maxn];

int id,head[maxn],visit[maxn],dist[maxn];

void init()
{
    fill(head,head+maxn,-1);
}

void addedge(int u,int v,int w)
{
    edges[id].v=v;
    edges[id].w=w;
    edges[id].next=head[u];     //指向u节点的第一条边
    head[u]=id++;    //替换这个第一条边
}

void spfa(int st)
{
    fill(visit,visit+maxn,0);
    fill(dist,dist+maxn,-INF);

    queue<int> Q;
    visit[st]=1;
    dist[st]=0;
    Q.push(st);
    while (!Q.empty())
    {
        int now=Q.front();
        Q.pop();

        visit[now]=0;
        for(int i=head[now];i!=-1;i=edges[i].next)
        {
            int v=edges[i].v;
            int w=edges[i].w;
            if(dist[v]<dist[now]+w)
            {
                dist[v]=dist[now]+w;
                if(!visit[v])
                {
                    Q.push(v);
                    visit[v]=1;
                }
            }
        }
    }
}

void solve()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        init();
        id=0;
        int maxnum=0,minnum=INF;
        int u,v,w;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d %d",&u,&v,&w);
            maxnum=max(maxnum,v+1);
            minnum=min(minnum,u);
            addedge(u,v+1,w);    //坐标向后面移一位
        }
        for(int i=minnum;i<maxnum;i++)
        {
            addedge(i,i+1,0);
            addedge(i+1,i,-1);   //隐含信息，每一个节点只有最多只能存放一个点
        }
        spfa(minnum);
        printf("%d\n",dist[maxnum]);
    }
}

int main()
{
    freopen("input.txt","r",stdin);
    solve();
    return 0;
}