模板

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

题目链接：AcWing 848。

本题就是要按照入度由小到大排序。

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
#include <cstring>
#include <iostream>
using namespace std;

const int N = 1e5+10;
int h[N], e[N], ne[N], idx, d[N];
int n, m;
int q[N];

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

bool topsort() {
    int tt = -1, hh = 0;
    for (int i = 1; i <= n; i++) {
        // 这里是 d[i] 代表第 i 节点的入度 所以从 1 ~ n 而不是从 0 开始
        if (d[i] == 0) q[++tt] = i;
    }
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; i  != -1; i = ne[i]) {
            int j = e[i];
            d[j]--;
            // 添加到队列中的是树的节点
            if (d[j] == 0) q[++tt] = j;
        }
    }
    // 如果所有节点都被遍历过，那么拓扑序列是存在的
    return tt == n-1;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        add(a, b);
    }
    if (topsort()) {
        for (int i = 0; i < n; i++) cout << q[i] << ' ';
    } else puts("-1");
}

[CSP-S2020] 函数调用

某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：

  1. 将数据中的指定元素加上一个值；
  2. 将数据中的每一个元素乘以一个相同值；
  3. 依次执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。

输入格式

第一行一个正整数 nn，表示数据的个数。

第二行 nn 个整数，第 ii 个整数表示下标为 ii 的数据的初始值为 aia_i。

第三行一个正整数 mm，表示数据库应用程序提供的函数个数。函数从 1∼m1 \sim m 编号。

接下来 mm 行中，第 jj（1≤j≤m1 \le j \le m）行的第一个整数为 TjT_j，表示 jj 号函数的类型：

  1. 若 Tj=1T_j = 1，接下来两个整数 Pj,VjP_j, V_j 分别表示要执行加法的元素的下标及其增加的值；
  2. 若 Tj=2T_j = 2，接下来一个整数 VjV_j 表示所有元素所乘的值；
  3. 若 Tj=3T_j = 3，接下来一个正整数 CjC_j 表示 jj 号函数要调用的函数个数，随后 CjC_j 个整数 g1(j),g2(j),…,gCj(j)g^{(j)}_1, g^{(j)}_2, \ldots , g^{(j)}_{C_j} 依次表示其所调用的函数的编号。

第 m+4m + 4 行一个正整数 QQ，表示输入的函数操作序列长度。

第 m+5m + 5 行 QQ 个整数 fif_i，第 ii 个整数表示第 ii 个执行的函数的编号。

输出格式

一行 nn 个用空格隔开的整数，按照下标 1∼n1 \sim n 的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。答案对 998244353\boldsymbol{998244353} 取模。

对于所有数据：0≤ai≤1040 \le a_i \le 10^4，Tj∈{1,2,3}T_j \in \{1,2,3\}，1≤Pj≤n1 \le P_j \le n，0≤Vj≤1040 \le V_j \le 10^4，1≤gk(j)≤m1 \le g^{(j)}_k \le m，1≤fi≤m1 \le f_i \le m。

首先可以把所有初始化操作看作一个 ai+va_i+v 的一号函数，然后把这些初始化与调用序列共同分配给超级节点 00，最后我们只要调用 00 号函数就行了。

如果没有三号函数，对于下面这个操作序列：

(a1+2)(×3)(a2+5)(×2)(a_1+2)(\times 3)(a_2+5)(\times 2)

假设所有初始值 ai=0a_i=0，相当于 a1+2×3×2,a2+5×2a_1+2\times3\times 2,a_2+5\times 2，也就是后面的乘会影响前面的加。这让我们想到倒序处理每个序列，并且记录下这一路上都乘了多少，更新 addadd 值。特别地，三号函数的 mulmul 是它所有子结点的 mulmul 之积，这也符合要求。

如果你只这么做，就会获得 10pts 的成绩，原因是一个函数会在不同的地方被调用多次，而我们并没有考虑如何正确记录一个函数被调用的次数。

显然，假设一个函数的父结点（也就是调用它的函数）被调用的次数为 pp，这个函数在这个序列中经过乘法等价调用的次数为 qq，那么最终调用的次数就是 pqpq，然后在多个地方都这样考虑，把结果累加起来。

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
96
97
98
99
100
101
102
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 200010, M = 1200010, P = 998244353;
int topo[N];
int h[N], e[M], ne[M], cnt[N], add[N], mul[N], type[N], din[N], p[N], idx;
int val[N/2];
int n, m, q;

void addedge(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    din[b]++;
}

void topsort() {
    int hh = 0, tt = -1;
    for (int i = 0; i <= n+m; i++) {
        if (din[i] == 0) topo[++tt] = i;
    }

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

void pushup() {
    for (int i = n+m; ~i; i--) {
        int u = topo[i];
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            mul[u] = (LL)mul[u] * mul[j] % P;
        }
    }
}

void pushdown() {
    for (int i = 0; i <= n+m; i++) {
        LL prod = 1;
        int u = topo[i];
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            cnt[j] = (cnt[j] + prod * cnt[u]) % P;
            prod = prod * mul[j] % P;
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    type[0] = 3;
    for (int i = 1; i <= n; i++) {
        type[i] = 1, p[i] = i;
        scanf("%d", &add[i]);
        addedge(0, i);
    }

    scanf("%d", &m);
    fill(mul, mul+n+m+1, 1);
    for (int i = 1; i <= m; i++) {
        int u = i+n;
        scanf("%d", &type[u]);
        if (type[u] == 1) scanf("%d%d", &p[u], &add[u]);
        if (type[u] == 2) scanf("%d", &mul[u]);
        if (type[u] == 3) {
            int c, f;
            scanf("%d", &c);
            while (c--) {
                scanf("%d", &f);
                addedge(u, f+n);
            }
        }
    }

    scanf("%d", &q);
    for (int i = 1, f; i <= q; i++) {
        scanf("%d", &f);
        addedge(0, f+n);
    }

    cnt[0] = 1;
    topsort();
    pushup();
    pushdown();

    for (int i = 0; i <= n+m; i++)
        if (type[i] == 1)
            val[p[i]] = (val[p[i]] + (LL)add[i] * cnt[i]) % P;

    for (int i = 1; i <= n; i++) printf("%d ", val[i]);
    puts("");

    return 0;
}

[NOIP2013] 车站分级

一条单向的铁路线上，依次有编号为 1,2,…,n 个火车站。

每个火车站都有一个级别，最低为 1 级。

现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 x，则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点） 。

现有 m 趟车次的运行情况（全部满足要求），试推算这 n 个火车站至少分为几个不同的级别。

题目保证一定有解。

题目链接：AcWing 456，P1983。

题目给了一个表，我偷个懒就不弄过来了，大家可以点题目链接到洛谷或者 AcWing 去看。

给出的暗示很明显了，始发站、终点站之间的所有停靠的车站等级 lsl_s 必须严格大于没停靠的车站 lel_{e}，这可以用反证法说明：如果 le≥lsl_e \ge l_s 那么它也必须停靠，构成矛盾，因此我们的结论是正确的。

所以本题差分约束的不等式组就是：

∀s,e∈[start,stop],ls≥le+1\forall s,e\in[start,stop], l_s\ge l_e+1

如果 mm 趟列车都从 1→n1 \to n 行驶，中间停靠了 xx 站，那么总共建的边数就是：

mx(n−x)≤mn24≤1094mx(n-x)\le \frac{mn^2}{4}\le\frac{10^9}{4}

这显然会爆内存的，就算不爆内存循环这么多次也要 TLE，因此这里再次用到虚拟结点 vv，让 ls≥lv≥le+1l_s\ge l_v \ge l_e+1，这样边的数量就是：

m[x+(n−x)]=mn≤106m[x+(n-x)]=mn\le 10^6

这就符合要求了。

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 2010, M = 1000010;
int n, m;
int h[N], e[M], ne[M], w[M], din[N], dist[N], idx;
bool st[N];
int q[N];

int read() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while ('0' <= ch && ch <= '9') {
        x = x*10 + (ch & 15);
        ch = getchar();
    }
    return x;
}

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

void topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= m+n; i++) {
        if (din[i] == 0) q[++tt] = i, dist[i] = 1;
    }
    
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--din[j] == 0) q[++tt] = j;
        }
    }
}

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

int main() {
    n = read(), m = read();
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        memset(st, 0, sizeof st);
        int cnt = read();
        int start = n, end = 0;
        while (cnt--) {
            int x = read();
            st[x] = true;
            start = min(start, x), end = max(end, x);
        }
        
        int v = n+i;
        for (int j = start; j <= end; j++)
            if (st[j]) add(v, j, 0);
            else add(j, v, 1);
    }
    topsort();
    printf("%d\n", solve());
    return 0;
}