《信息学奥赛一本通·高手专项训练》集训 Day 11

· · 个人记录

最短路径

\color{Green}100\color{Black}+\color{Blue}0\color{Black}+\color{Red}0\color{Black}=\color{Orange}100\color{Black}/\text{Rank 13}

蓝色的 \color{Blue}\text{0} 是因为一百分的代码中间加了个字符 \texttt{A}，\text{CE} 了。

\color{#FFC116}\text{A. 简单游走}

题目

有一张 n 个点，m 条边的无向图，点从 1 到 n 标号。

时刻 0 时，你在结点 1。你需要用最少的时间从结点 1 走到结点 n。通过 m 条边中的每一条都要花一定的时间。

每个结点会有可能在某些时刻被限制。一个结点 x 在时刻 T 被限制，意味着这个结点的人在时刻 T 不能从这个点 x 走出去。

你只能在整数时刻进出某个结点，一个结点可以逗留任意非负整数时间。

现在，请问你最少需要多少时间能从结点 1 走到结点 n。

题解

显然，即使有了限制，仍然是更早到达的点更优，于是我们可以用 \text{Dijkstra} 求出一个点最早到达的时间，暴力计算它最早出发的时间即可，因为限制的时间很少，所以不会超时。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 510, M = 1010;
int n, m, k[N], d[N], v[N];
int head[N], ver[M << 1], edge[M << 1], nxt[M << 1], tot;
vector<int> t[N];
void add(int x, int y, int z) {
    ver[++tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
void Dijkstra(int s) {
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    priority_queue<pair<int, int> > q;
    d[s] = 0;
    q.push(make_pair(0, s));
    while (q.size()) {
        int x = q.top().second;
        q.pop();
        if (v[x])
            continue;
        v[x] = 1;
        if (x != n) {
            int j = lower_bound(t[x].begin(), t[x].end(), d[x]) - t[x].begin();
            while (0 <= j && j < t[x].size() && t[x][j] == d[x]) {
                j++;
                d[x]++;
            }
        } else {
            return;
        }
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                q.push(make_pair(-d[y], y));
            }
        }
    }
}
int main() {
    freopen("travel.in", "r", stdin);
    freopen("travel.out", "w", stdout);
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        u = read();
        v = read();
        w = read();
        add(u, v, w);
        add(v, u, w);
    }
    for (int i = 1; i <= n; i++) {
        k[i] = read();
        for (int j = 1; j <= k[i]; j++) t[i].push_back(read());
        sort(t[i].begin(), t[i].end());
    }
    Dijkstra(1);
    write(d[n]);
    return 0;
}

\color{#3498DB}\text{B. 路径之和}

题目

对于一张有向图，定义 d(x,y,z) 为从 x 号点出发，不经过 y 号点，最终到达 z 号点的最短路径长度，如果不存在这样的路径，d(x,y,z) 的值为 -1。

现在给定有向图中每两个点之间的有向边长度，求对于所有满足 1\le x,y,z\le n(x\neq y,y\neq z) 的有序数对 ，求它们 d(x,y,z) 的和。

也就是求对于每个 y，求除了 y 之外，其余的所有点组成的有序点对 (x,z) 不经过 y 的最短路长度之和（不存在即为 -1）。

题解

这样，计算不经过 $y$ 的有序点对 $(x,z)$ 对答案的贡献 $dist(x,z)$ 时，只要计算 $i\in\{[1,y-1]\cup[y+1,n]\}$ 对 $dist(x,z)$ 的更新情况即可，可以使用 $\text{cdq}$ 分治解决。 具体来说，我们计算区间 $[l,r]$ 的 $y$ 的 $dist(x,z)$，只要进行下面的步骤： 1. 枚举 $l\le k\le mid$，更新这些 $k$ 对 $dist(x,z)$ 的影响，递归右区间 $[mid+1,r]$。 1. 撤销这些影响。 1. 枚举 $mid+1\le k\le r$，更新这些 $k$ 对 $dist(x,z)$ 的影响，递归左区间 $[l,mid]$。 递归到长度为 $1$ 的区间时，就可以累加答案了。 ### 代码 ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; long long read() { long long x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } return x * f; } void write(long long x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } const int N = 330; int n, v[N], a[N][N]; ll ans, d[N]; void solve(int l, int r) { if (l == r) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != l && j != l && i != j) { if (a[i][j] >= 0x3f3f3f3f) ans--; else ans += a[i][j]; } } } return; } int tmp[N][N]; int mid = (l + r) >> 1; memcpy(tmp, a, sizeof(tmp)); for (int k = l; k <= mid; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != k && k != j && i != j) { a[i][j] = min(a[i][j], a[i][k] + a[k][j]); } } } } solve(mid + 1, r); memcpy(a, tmp, sizeof(a)); for (int k = mid + 1; k <= r; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != k && k != j && i != j) { a[i][j] = min(a[i][j], a[i][k] + a[k][j]); } } } } solve(l, mid); } int main() { freopen("sum.in", "r", stdin); freopen("sum.out", "w", stdout); n = read(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = read(); if (a[i][j] == -1) a[i][j] = 0x3f3f3f3f; } } solve(1, n); write(ans); return 0; } ``` ## $\color{#3498DB}\text{C. 宝藏寻觅}

题目

给定一张有向图，每条边有边权，为 0 或 1，可能有重边或自环，点的编号从 1 开始。

现在给你一个无限长的序列，生成方式如下：

  1. 序列开始仅有一个元素 \texttt{0}；
  2. 一次操作为：将序列的所有元素取出，将取出的部分取反（\texttt{0} 取反为 \texttt{1}，\texttt{1} 取反为 \texttt{0}），取反后接在原序列后。例如序列 \texttt{0110} 经过操作为 \texttt{01101001}；
  3. 执行无穷多次操作即生成了这个序列。

这个序列的前几位为 \texttt{0110100110010110……}

现在你需要找到一条起点为 1，经过边数最多的路径（可以经过重复点和边），使得路径中经过的第 i 条边的边权与这个序列的第 i 位相同。

若最长的路径经过的边数超过 10^{18}，输出 -1。

题解

这个序列有一个很好的性质：第 2^i+1\sim 2^{i+1} 项就是第 1\sim2^i 项取反。

于是设 f_{i,u,v} 表示能否通过原来的序列（第 1\sim 2^i 项）从 u 走 2^i 步到点 v，g_{i,u,v} 表示能否通过取反的序列（第 2^i+1\sim 2^{i+1} 项）从 u 走 2^i 步到点 v。那么：

f_{i,u,v}=f_{i-1,u,k}\lor g_{i-1,k,v} g_{i,u,v}=g_{i-1,u,k}\lor f_{i-1,k,v}

预处理出 f 数组和 g 数组，我们就可以用倍增求出答案，即一直试能不能走 2^k(k=59\rightarrow1) 步，同时维护当前是在原来的序列上走还是取反的序列上走，走一次后将其异或上 1 即可。

由于状态转移的都是 \texttt{0/1} 数组，于是我们可以使用 \texttt{bitset} 进行优化，时间复杂度为 O(\frac{n^3\log 10^{18}}{w})，其中 w 为字长。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 110, K = 60;
int n, m, t;
bitset<N> f[K][2][N], now, nxt;
ll ans;
void build(bitset<N> a[N], bitset<N> b[N], bitset<N> c[N]) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (b[i][j])
                a[i] |= c[j];
}
int main() {
    freopen("treasure.in", "r", stdin);
    freopen("treasure.out", "w", stdout);
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        x = read();
        y = read();
        z = read();
        f[0][z][x][y] = 1;
    }
    for (int i = 1; i <= 59; i++) {
        build(f[i][0], f[i - 1][0], f[i - 1][1]);
        build(f[i][1], f[i - 1][1], f[i - 1][0]);
    }
    now[1] = 1;
    for (int i = 59; i >= 0; i--) {
        nxt.reset();
        for (int j = 1; j <= n; j++)
            if (now[j])
                nxt |= f[i][t][j];
        if (nxt.count()) {
            now = nxt;
            ans |= (1ll << i);
            t ^= 1;
        }
    }
    if (ans > 1e18)
        puts("-1");
    else
        write(ans);
    return 0;
}

强连通分量

\color{Red}0\color{Black}+\color{Green}85\color{Black}+\color{Green}100\color{Black}=\color{Orange}185\color{Black}/\text{Rank 9}

\color{#52C41A}\text{A. 网格游走}

题目

有一个由 n 行 m 列的 1\times 1 的格子组成的矩阵，每个格子 (i,j) 有对应的高度 h_{i,j} 和初始的一个非负整数权值 v_{i,j}。

你可以随便选择一个格子作为起点，然后在接下来的每一步当中，能且只能到达与当前格子有边相邻的四个格子中的高度不超过当前格子高度的格子，每当到达一个新格子（包括一开始选择的初始格子），就能将该格子的权值加入到你的得分中，然后该格子的权值就会等概率随机变成不比当前的权值大的一个非负权值。

每一个格子在满足条件的情况下，可以走任意多次。

我们希望得到一条路径，使得这个路径的期望总得分最大，请求出这个最大期望总得分。

请注意，这条路径可以是无限长的。

题解

显然，相同高度的格子构成的连通块是可以每个都走无限遍的，于是我们可以求出每个连通块，将其缩点，计算整个点的期望，接着原图就变成了一个 \text{DAG}，直接拓扑排序求最长路即可。

问题是如何求一个连通块的期望得分呢？若该连通块只有一个点，那么只能走一次，期望得分就是 v 的值，否则，里面的每个点都能走无穷遍，把每个点的期望得分 f(v_{i,j}) 相加即可。

那么如何求 f(i) 呢？显然有 f(i)=i+\frac{1}{i+1}\sum_{j=0}^if_j，因此

\frac{i}{i+1}f(i)=i+\frac{1}{i+1}\sum_{j=0}^{i-1}f_j f(i)=\frac{i+1}{i}(i+\frac{1}{i+1}\sum_{j=0}^{i-1}f_j)=i+1+\frac{1}{i}\sum_{j=0}^{i-1}f_j

设 S_i=\sum_{j=0}^{i}f_j，那么：

S_{i-1}=if_i-i\times(i+1) S_{i}=(i+1)f_{i+1}-(i+1)\times(i+2)

两式相减得：

(i+1)f_{i+1}=(i+1)f_{i}+2(i+1) f_{i+1}=f_{i}+2

显然 f_0=0，因此 f_i=2i。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1010;
int n, m, num, in[N * N], h[N][N], v[N][N], sze[N * N], vis[N][N];
int fx[4] = { 0, 0, 1, -1 }, fy[4] = { 1, -1, 0, 0 }, wh[N * N];
int head[N * N << 1], ver[N * N << 1], nxt[N * N << 1], tot;
ll sum[N * N], mx[N * N], ans;
void add(int x, int y) {
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
    in[y]++;
}
bool check(int x, int y) { return x >= 1 && y >= 1 && x <= n && y <= m; }
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + fx[i], yy = y + fy[i];
        if (!check(xx, yy) || (h[xx][yy] ^ h[x][y]) || vis[xx][yy])
            continue;
        vis[xx][yy] = num;
        sze[num]++;
        sum[num] += v[xx][yy];
        dfs(xx, yy);
    }
}
int main() {
    freopen("road.in", "r", stdin);
    freopen("road.out", "w", stdout);
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) h[i][j] = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) v[i][j] = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (!vis[i][j]) {
                vis[i][j] = ++num;
                sze[num] = 1;
                wh[num] = h[i][j];
                sum[num] = v[i][j];
                dfs(i, j);
            }
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k < 4; k++) {
                int xx = i + fx[k], yy = j + fy[k];
                if (!check(xx, yy) || vis[i][j] == vis[xx][yy])
                    continue;
                if (wh[vis[xx][yy]] > wh[vis[i][j]])
                    add(vis[xx][yy], vis[i][j]);
            }
        }
    queue<int> q;
    for (int i = 1; i <= num; i++) {
        if (!in[i]) {
            mx[i] = sum[i] + sum[i] * (sze[i] != 1);
            q.push(i);
        }
    }
    while (q.size()) {
        int x = q.front();
        q.pop();
        ans = max(ans, mx[x]);
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            mx[y] = max(mx[y], mx[x]);
            in[y]--;
            if (!in[y]) {
                mx[y] += sum[y] + sum[y] * (sze[y] != 1);
                q.push(y);
            }
        }
    }
    write(ans);
    return 0;
}

\color{#52C41A}\text{B. 染色研究}

题目

小翔有一个包含 n 个点，m 条边的有向图。起初这张有向图上的每个点都是白色的。

最近小翔想要给这张有向图上的每个点都染上黑色。他可以进行若干轮的染色，每一轮的染色规则如下：

现在，小翔想请你计算出，最少要进行几轮染色，才可以使得这张有向图上的每个点都被染上色。

题解

显然一个强联通分量里的点是可以互相到达的，不能同时染，于是我们将其缩点，缩后的点要染的次数就是这个点里的点数。

缩点后，原图变成了一个 \text{DAG}，易证 \text{DAG} 上的最长链就是答案。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10;
int n, m, cnt, c[N], top, stak[N];
int head[N], nxt[N << 1], ver[N << 1], tot;
int num, dfn[N], low[N], ins[N];
int in[N], sze[N], mx[N];
void add(int x, int y) { ver[++tot] = y, nxt[tot] = head[x], head[x] = tot; }
void tarjan_scc(int x) {
    dfn[x] = low[x] = ++num;
    ins[stak[++top] = x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan_scc(y);
            low[x] = min(low[x], low[y]);
        } else if (ins[y])
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        int y;
        cnt++;
        do {
            ins[y = stak[top--]] = 0;
            // scc[cnt].push_back(y);
            sze[cnt]++;
            c[y] = cnt;
        } while (x != y);
    }
}
void work_scc() {
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan_scc(i);
}
int hc[N << 1], nc[N << 2], vc[N << 2], tc;
void add_c(int x, int y) {
    vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc;
    in[y]++;
}
void work_shscc() {
    for (int x = 1; x <= n; x++)
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (c[x] == c[y])
                continue;
            add_c(c[y], c[x]);
        }
}
void topu() {
    queue<int> q;
    for (int i = 1; i <= cnt; i++) {
        if (!in[i]) {
            mx[i] += sze[i];
            q.push(i);
        }
    }
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = hc[x]; i; i = nc[i]) {
            int y = vc[i];
            mx[y] = max(mx[y], mx[x]);
            in[y]--;
            if (!in[y]) {
                mx[y] += sze[y];
                q.push(y);
            }
        }
    }
}
int main() {
    freopen("bomb.in", "r", stdin);
    freopen("bomb.out", "w", stdout);
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        int x, y;
        x = read();
        y = read();
        add(x, y);
    }
    work_scc();
    work_shscc();
    topu();
    int ans = 0;
    for (int i = 1; i <= cnt; i++) {
        ans = max(ans, mx[i]);
    }
    write(ans);
    return 0;
}

\color{#52C41A}\text{C. 银河灿星}

题目

题解

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10;
int n, m, cnt, c[N], top, stak[N];
int head[N], nxt[N << 1], ver[N << 1], edge[N << 1], tot;
int num, dfn[N], low[N], ins[N], cnt1, in[N];
ll sze[N], ans, mx[N];
void add(int x, int y, int z) { ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot; }
void tarjan_scc(int x) {
    dfn[x] = low[x] = ++num;
    ins[stak[++top] = x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan_scc(y);
            low[x] = min(low[x], low[y]);
        } else if (ins[y])
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        int y;
        cnt++;
        do {
            ins[y = stak[top--]] = 0;
            sze[cnt]++;
            c[y] = cnt;
        } while (x != y);
    }
}
void work_scc() {
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan_scc(i);
}
int hc[N], nc[N << 1], vc[N << 1], ec[N << 1], tc;
void add_c(int x, int y, int z) {
    vc[++tc] = y, ec[tc] = z, nc[tc] = hc[x], hc[x] = tc;
    in[y]++;
}
void work_shscc() {
    for (int x = 1; x <= n; x++)
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (c[x] == c[y])
                continue;
            add_c(c[x], c[y], edge[i]);
            if (edge[i] == 1)
                cnt1--;
        }
}
void topu() {
    queue<int> q;
    for (int i = 1; i <= cnt; i++) {
        if (!in[i]) {
            add_c(0, i, 1);
        }
    }
    q.push(0);
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = hc[x]; i; i = nc[i]) {
            int y = vc[i];
            mx[y] = max(mx[y], mx[x] + ec[i]);
            in[y]--;
            if (!in[y]) {
                ans += mx[y] * sze[y];
                q.push(y);
            }
        }
    }
}
int main() {
    freopen("galaxy.in", "r", stdin);
    freopen("galaxy.out", "w", stdout);
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        int t, x, y;
        t = read();
        x = read();
        y = read();
        if (t == 1) {
            add(x, y, 0);
            add(y, x, 0);
        } else if (t == 2)
            add(x, y, 1), cnt1++;
        else if (t == 3)
            add(y, x, 0);
        else if (t == 4)
            add(y, x, 1), cnt1++;
        else if (t == 5)
            add(x, y, 0);
    }
    work_scc();
    work_shscc();
    if (cnt1 != 0) {
        puts("-1");
        return 0;
    }
    topu();
    write(ans);
    return 0;
}