CF22D 题解

Vitamin_B · 2024-06-20 21:34:48 · 题解

思路

首先在看这题前你得学会差分约束，类似 P1250。

先建立几个不等式（a_x 表示 1\sim x 中最少有几个点）：

就建这么几条边跑一个 SPFA 就行啦！

注意事项

首先可能 l>r，建边前要先交换。

然后 l,r 可能是负数，可以先在建边时 +10001，输出时减掉。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
int n, m, x, y, dis[20005];
vector <pii> v[20005];
bitset <20005> vis;
queue <int> q;
int main () {
    ios::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    cin >> m;
    while (m --) {
        cin >> x >> y;
        if (x > y)
            swap (x, y);
        x += 10001, y += 10001;
        v[x - 1].push_back ({y, 1});
        n = max (n, y);
    }
    for (int i = 0; i < n; ++ i)
        v[i].push_back ({i + 1, 0}), v[i + 1].push_back ({i, -1});
    fill (dis + 1, dis + 1 + n, -1);
    q.push (0);
    while (! q.empty ()) {
        x = q.front ();
        q.pop ();
        vis[x] = 0;
        for (pii& i : v[x])
            if (i.second + dis[x] > dis[i.first]) {
                dis[i.first] = dis[x] + i.second;
                if (! vis[i.first])
                    q.push (i.first), vis[i.first] = 1;
            }
    }
    cout << dis[n] << '\n';
    for (int i = 1; i <= n; ++ i)
        if (dis[i] > dis[i - 1])
            cout << i - 10001 << ' ';
    return 0;
}