知识点

应用一 :求不等式组的可行解

前提条件：从源点出发，一定可以走到所有的边！！！！注意是边！！！

步骤

  1. 先将每个不等式 xi≤xj+ck，转化成一条从 xj走到 xi，长度为 ck 的边。
  2. 找到一个超级源点，使得该源点一定可以遍历到所有边
  3. 从源点求一遍单源最短路

结果1

如果存在负环，则原不等式组一定无解

结果2

如果没有负环，则 dist[i]就是原不等式组的一个可行解

应用二: 求最大值或者最小值

结论：如果求的是最小值，则应该求最长路；如果求的是最大值，则应该求最短路。

问题：如何转化 xi≤c，其中 c 是一个常数，这类的不等式。

方法：建立一个超级源点0，然后建立 0 -> i 的边，长度是 c 即可。

糖果

题意

给小朋友分糖果，小朋友分的糖果之间有几种关系，求最少消耗的糖果。

思路

“每个小朋友都要分到糖果”，说明都大于等于1。超级原点都连权重为1的边。

几种情况对应一下建图，求最长路。

代码

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 300010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL dist[N];
int q[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool spfa()
{
    int hh = 0, tt = 1;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    q[0] = 0;
    st[0] = true;

    while (hh != tt)
    {
        int t = q[ -- tt];
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return false;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    st[j] = true;
                }
            }
        }
    }

    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) add(b, a, 0), add(a, b, 0);
        else if (x == 2) add(a, b, 1);
        else if (x == 3) add(b, a, 0);
        else if (x == 4) add(b, a, 1);
        else add(a, b, 0);
    }

    for (int i = 1; i <= n; i ++ ) add(0, i, 1);

    if (!spfa()) puts("-1");
    else
    {
        LL res = 0;
        for (int i = 1; i <= n; i ++ ) res += dist[i];
        printf("%lld\n", res);
    }

    return 0;
}

总结

注意求最长路的方法，初始化dis[]为正无穷，spfa，小了就更新。

区间

题意

给定 $n$ 个区间 $\left[a_{i}, b_{i}\right]$ 和 $n$ 个整数 $c_{i}$ 。
你需要构造一个整数集合 $Z$, 使得 $\forall i \in[1, n], Z$ 中满足 $a_{i} \leq x \leq b_{i}$ 的整数 $x$ 不少于 $c_{i}$ 个。 求这样的整数集合 $Z$ 最少包含多少个数。

思路一：差分约束

因为求最少包含的数，所以求最长路，注意建图方式。

  • 考虑前缀和, 因为前缀和中 $\mathrm{S}[0]=0$, 所有这里将 $a_{i}, b_{i}$ 所在的区间范围加上一个 1 , 区间范围变成了[1, 50001], 这样并不影响最终的结果。
  • S[i]表示：1到 i 中被选出数的个数。我们最终要求解的就是 $S_{50001}$ 的最小值, 因此需要使用最长路径。
  • 对于S, S需要满足如下条件:
    (1) $S_{i} \geq S_{i-1}, 1 \leq i \leq 50001$; 即 i-1 到 i 有长度为0的边
    (2) $S_{i}-S_{i-1} \leq 1 \Longleftrightarrow S_{i-1} \geq S_{i}-1$; 即 i 到 i-1 有长度为1的边
    (3) 区间[a, b]中至少有c个数 $\Longleftrightarrow S_{b}-S_{a-1} \geq c \Longleftrightarrow S_{b} \geq S_{a-1}+c$; 即 a-1 到 b 有长度为c的边
  • 需要验证一下：从源点出发，是否一定可以走到所有的边。根据条件（1），从i-1可以走到i，因此从0可以走到1，从1可以走到2，……，因此存在这样的源点。
  • 求最长路即可

代码

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <map>
#include <vector>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int n,a,b,c;
vector<PII> mp[500010];
int dis[500010];
bool st[500010];
queue<int> qu;
void spfa(){
    memset(dis,-0x3f,sizeof dis);
    st[0]=true;
    qu.push(0);
    dis[0]=0;
    while(!qu.empty()){
        int tt=qu.front();
        qu.pop();
        st[tt]= false;

        for(PII pit:mp[tt]){
            int nx=pit.second,dd=pit.first;
            if(dis[nx]<dis[tt]+dd){
                dis[nx]=dis[tt]+dd;
                if(!st[nx]){
                    st[nx]=true;
                    qu.push(nx);
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=50001;i++){
        mp[i-1].push_back({0,i});
        mp[i].push_back({-1,i-1});
    }
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a,&b,&c);
        a++,b++;
        mp[a-1].push_back({c,b});
    }
    spfa();
    printf("%d",dis[50001]);
    return 0;
}

思路二：贪心

考虑把所有线段按照右端点 bb 从小到大排序，依次考虑每一条线段的要求：

  • 如果已经满足要求则跳过
  • 否则尽量选择靠后的数（因为之后的线段的右端点都在这条线段的右边，这样容错更高）
  • 所以，我们可以建一个数组，d[i] 表示 i 数字是否选择（填1或0），扫一遍 [l,r] 区间求和，然后从后往前贪心放数即可。

代码

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;
int n, d[N], c[N];
struct Seg{
    int a, b, c;
    bool operator < (const Seg &x) const {
        return b < x.b;
    }
}e[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
    sort(e + 1, e + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int l = e[i].a, r = e[i].b, cnt = e[i].c;
        for (int j = l; j <= r; j++)
            cnt -= d[j];
        if(cnt > 0) {
            for (int j = r; j >= l && cnt; j--)
                if(!d[j]) cnt--, ans++, d[j] = 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

排队布局

题意

农夫约翰有 N 头奶牛，编号从 1到 N，沿一条直线站着等候喂食。

奶牛排在队伍中的顺序和它们的编号是相同的。可能有两头或者更多奶牛站在同一位置上。

一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数 L。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数 D。

你的工作是：

  • 如果不存在满足要求的方案，输出-1；
  • 如果 1 号奶牛和 N 号奶牛间的距离可以任意大，输出-2；
  • 否则，计算出在满足所有要求的情况下，1 号奶牛和 N 号奶牛间可能的最大距离。

思路

建图:

每头奶牛按编号排序 i+1 → i w = 0 x[i] ≤ x[i+1]
两者之间的距离不超过一个给定的数L a → b w = L x[b] ≤ x[a] + L
两者之间的距离不小于一个给定的数D x[a] ≤ x[b]-D b → a w = -D

问题1:

因为要求负环，提前将所有点加入队列。

  • 如果没有负环-有解
  • 如果有负环-无解

问题2：

将x[1]固定为0，求最短路。看1到n的距离是否为正无穷。

问题3：

输出看1到n的距离

代码

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 10000 + 10000 + 1000 + 10, INF = 0x3f3f3f3f;

int n, m1, m2;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa(int size)
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);

    for (int i = 1; i <= size; i ++ )
    {
        q[tt ++ ] = i;
        dist[i] = 0;
        st[i] = true;
    }

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d%d", &n, &m1, &m2);
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i ++ ) add(i + 1, i, 0);
    while (m1 -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a > b) swap(a, b);
        add(a, b, c);
    }
    while (m2 -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a > b) swap(a, b);
        add(b, a, -c);
    }

    if (spfa(n)) puts("-1");
    else
    {
        spfa(1);
        if (dist[n] == INF) puts("-2");
        else printf("%d\n", dist[n]);
    }
    return 0;
}

车站分级（差分约束+建图优化+拓扑排序）

思考

差分约束

所有末停靠的即为级别低, 记为 $A$，所有停靠的站点级别一定比 $A$ 的高, 记作 $B$
得到公式 $B \geq A+1$
根据很明显是一道差分约束问题。

因为所有车站级别都是正值, 所以 $A \geq 1$, 也就是从向所有的 $A$ 中的点连一条权值为 1 的 有向边。我们常常用直接给 dist 数组赋值为1代替。

但是由于实际数据范围较大
最坏情况下是有 1000 趟火车, 每趟有 1000 个点, 每趟上限有 500 个点停站, 则有 $(1000-500)$ 个点不停站, 不停站的点都向停站的点连有向边, 则总共有 $500 500 1000=2.5 * 10^{8}$, 差分约束的 spfa 有可能超时。

建图优化

如果直接暴力建图就会建 $O(n m)$ 条边, 也就是 $2 * 10^{8}$ 个点，时间和空间都有可能超时。
我们可以在中间建一个虚拟节点, 左边向虚拟点连0, 虚拟点向右边连1等价于左边向右边 连1
这样只会建 $O(n+m)$ 条边
注意的是本题一共 $m$ 条线路,每条线路一个虚拟源点,所以一共会有 $n+m$ 个点。
如下图所示：

拓扑排序求最长路

用传统的SPFA最长路做法会超时，所以考虑拓扑排序。

由于本题中的所有点的权值都是大于 0 , 并且一定满足要求 $=>$ 所有车站都等级森严 $=>$ 不存在环 $=>$ 可以拓扑排序得到拓扑图，使用递推求得最长路。

即：先求拓扑序，由拓扑序递推最长路。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, M = 1000010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int q[N], d[N];
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    d[b] ++ ;
}

void topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n + m; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if ( -- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        memset(st, 0, sizeof st);
        int cnt;
        scanf("%d", &cnt);
        int start = n, end = 1;
        while (cnt -- )
        {
            int stop;
            scanf("%d", &stop);
            start = min(start, stop);
            end = max(end, stop);
            st[stop] = true;
        }

        int ver = n + i;
        for (int j = start; j <= end; j ++ )
            if (!st[j]) add(j, ver, 0);
            else add(ver, j, 1);
    }

    topsort();

    for (int i = 1; i <= n; i ++ ) dist[i] = 1;
    for (int i = 0; i < n + m; i ++ )
    {
        int j = q[i];
        for (int k = h[j]; ~k; k = ne[k])
            dist[e[k]] = max(dist[e[k]], dist[j] + w[k]);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);

    printf("%d\n", res);

    return 0;
}