NC9985A美丽的路径

Question

给定点权无向图，求任意由到的路径中最大的第小的点权。

Solution

二分答案，假设答案为，则对于第小的点权，我们将其转化为该路径上有的点，他们的点权值。
我们将路径上的点染色分为两种点：

1. ，染为。
2. ，染为。

有如下情况：
一. 与不联通，
二. 与联通，

1. 路径上存在两个连续的号点，则显然我们可以通过反复横跳，来无限增大路径的长度，则必然能够满足使得。
2. 
   由于上面的情况已经除去，所以目前来说最好的情况是间隔，此时反复横跳已经没有任何意义。
   a. ，则所求点为中位数，由于首尾为，所以，
   b. ,则所求点为第小的点权,，
3. 此时都有可能，我们DFS染色验证即可。

Code

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 2e5 + 5;

int n, m, s, t, a[N];
vector<int> G[N];
bool vis[N], f[N];

void dfs(int u) {
    vis[u] = true;
    for (auto v : G[u]) {
        if (!vis[v]) dfs(v);
    }
}

void DFS(int u, int x) {
    f[u] = true;
    for (auto v : G[u]) {
        if (!f[v] && max(a[u], a[v]) >= x) {
            DFS(v, x);
        }
    }
}

bool check(int x) {
    for (int i = 1; i <= n; i++) {
        if (vis[i] && a[i] >= x) {
            for (auto j : G[i]) {
                if (a[j] >= x) return true;
            }
        }
    }
    if (a[s] < x && a[t] < x) return false;
    memset(f, 0, sizeof(f));
    DFS(s, x);
    return f[t];
}

void solve() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        G[i].clear();
        vis[i] = false;
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(s);
    if (!vis[t]) {
        cout << "NO\n";
        return;
    } else {
        cout << "YES\n";
    }
    int L = 0, R = *max_element(a + 1, a + 1 + n) + 1, ans = 0;
    while (L < R) {
        int mid = (L + R) / 2;
        if (check(mid)) {
            ans = mid;
            L = mid + 1;
        } else {
            R = mid;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

Solution Update

经评论区提醒做出如下修改，反而没跑过去，我怀疑题目的数据是错的。

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 2e5 + 5;

int n, m, s, t, a[N];
vector<int> G[N];
int f[N];
bool vis[N];

void dfs(int u) {
    vis[u] = true;
    for (auto v : G[u]) {
        if (!vis[v]) dfs(v);
    }
}

void DFS1(int u, int x) {
    f[u] = 1;
    for (auto v : G[u]) {
        if (!f[v] && max(a[u], a[v]) >= x) {
            DFS1(v, x);
        }
    }
}

void DFS2(int u, int x) {
    if (f[u] == 1) {
        f[t] = 1;
        return;
    }
    f[u] = 2;
    for (auto v : G[u]) {
        if (f[v] != 2 && (f[v] == 1 || max(a[u], a[v]) >= x)) {
            DFS2(v, x);
        }
    }
}

bool check(int x) {
    for (int i = 1; i <= n; i++) {
        if (vis[i] && a[i] >= x) {
            for (auto j : G[i]) {
                if (a[j] >= x) return true;
            }
        }
    }
    if (a[s] < x && a[t] < x) return false;
    memset(f, 0, sizeof(f));
    DFS1(s, x);
    DFS2(t, x);
    return f[t] == 1;
}

void solve() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        G[i].clear();
        vis[i] = false;
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(s);
    if (!vis[t]) {
        cout << "NO\n";
        return;
    } else {
        cout << "YES\n";
    }
    int L = 0, R = *max_element(a + 1, a + 1 + n) + 1, ans = 0;
    while (L < R) {
        int mid = (L + R) / 2;
        if (check(mid)) {
            ans = mid;
            L = mid + 1;
        } else {
            R = mid;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}