题解：P7832 [CCO2021] Bread First Search

naughty-naught / 2024-10-15 / 原文

Problem Link

[CCO2021] Bread First Search

题意

给一个无向图，求要再加多少条边使得 $1 \sim n$ 是合法的 bfs 序。

Solution

首先考虑一个特殊情况：$1$ 与 $n$ 连了一条边。

那么 $1$ 和其他所有点都要连一条边。

把这个放到一般情况便有：

推论：若 $i$ 与 $j$（$i < j$）连了一条边，那么对于区间 $\left ( i, j\right )$ 的每个点，要么 $i$ 与其有一条直接连接的边，要么要加一条直接连接的边。

这样的话所有点会被分层，并且每一层的点是连续的同时相邻层的点编号也连续，不难想到定义 $f_{i,j}$ 为 $i$ 和 $j$ 在同一层时要加的最少边数，时间复杂度为 $O(n^3)$。

由推论，对于一个锚定的点 $i$，所有在一层的 $j$ 是连续的，可以用后缀进行维护，可以优化至 $O(n)$。

Code

//written by Naught
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define Maxn 200005
#define Inf 0x3f3f3f3f
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}

struct Edge
{
    int to, nxt;
}e[Maxn<<1];
int h[Maxn], cnt;

void add(int u, int v)
{
    e[++cnt] = {v, h[u]};
    h[u] = cnt;
}

int n, m, g[Maxn], f[Maxn], sum;
bool vis[Maxn];

void reach(int u) {sum += (vis[u]? 0 : 1), vis[u] = true;}

int main()
{
    n = read(), m = read();
    fo(i, 1, m)
    {
        int u = read(), v = read();
        g[u] = max(g[u], v), g[v] = max(g[v], u);
        add(u, v), add(v, u);
    }

    memset(f, Inf, sizeof(f));
    fo(i, 1, n) g[i] = max(g[i], g[i-1]);

    fo(i, 1, n-1)
    {
        f[i] = min(f[i], f[i-1]+1);
        reach(i);
        for(int j = h[i]; j; j = e[j].nxt)
        {
            int v = e[j].to;
            reach(v);
        }
        int lst = max(g[i], i+1);
        f[lst] = min(f[lst], (i == 1 ? 0 : f[i]) + lst - sum);
    }

    printf("%d", f[n]);

    return 0;
}