羁绊大师

#动态规划 #图论 #并查集 #背包

题目描述

在某一自走棋游戏中，胖胖龙此刻拥有 $n$ 个英雄，其中第 $i$ 个英雄拥有两种羁绊，分别为 $a_i,b_i(a_i<b_i)$
不存在两个英雄拥完全相同的两种羁绊，即对于 $1\le i<j\le n$, 有 $a_i\ne a_j$ 或 $b_i\ne b_j$ 。因为该游戏模式
的特殊性，一共具有 m 种羁绊，且每种羁绊至至至多多多只有两个英雄拥有。当胖胖龙处于等级 $L$ 时，可以选
择自己的 $L$ 个英雄上阵。对于每种羁绊，当且仅当上阵英雄中有两个英雄拥有此羁绊时，此羁绊为激活
状态。
胖胖龙的梦想是成为羁绊大师，他希望选出 $L$ 个英雄上阵，使得自己激活的羁绊种数尽可能多。胖胖龙
希望你能帮帮他，如果你帮助了他，他会给你跳一段节奏鲜明而富有动感的舞蹈。
请你分别对 L ∈ { 1 , 2 ⋅ ⋅ ⋅ n } L ∈ \{1, 2 · · · n\} L∈{1,2⋅⋅⋅n} 的 $n$种情况，分别输出激活羁绊的最大数量。

输入格式

第一行，包含两个非负整数 n, m(1 ≤ n ≤ 105, n ≤ m ≤ 2n) 分别表示胖胖龙此时拥有的英雄数量，以及
游戏中存在羁绊的数量。
接下来 n 行，第 i 行包含两个整数 ai, bi(1 ≤ ai < bi ≤ m) 分别表示第 i 个英雄拥有的两种羁绊。

输出格式

输出一行，包含 n 个整数，从左到右第 i 个整数表示当 L = i 时，胖胖龙最多能够激活的羁绊种数。整
数之间用一个用空格隔开。

样例 #1

样例输入 #1

10 10
1 2
2 3
1 3
4 5
5 6
6 7
4 7
8 9
9 10
8 10

样例输出 #1

0 1 3 4 4 6 7 7 8 10

解法

解题思路

对于一个英雄有两个羁绊，一个羁绊最多有两个英雄拥有。如果我们把羁绊看做一个点，英雄看做一条边，那么整张图只有环和链，不存在环中带链，因为每个点最多就两个度数。

那么，题目要求我们选择最多的羁绊，而这个羁绊必须被两个英雄共有才生效，转换在图中就是，环对应的贡献就是环的大小，链对应的贡献就是链的大小$-1$，因此我们要尽可能选多的环。

而对于环和链的维护，一种是建图后染色，一种是使用并查集，这里使用并查集来维护。

那么，我们可以把环看做物品，$L$看做背包容量，然后去跑背包。如果背包容量大于全部环
的大小，那么我们只需要判断能取多少个链即可，需要贪心地从大到小来取，因为要尽可能少的取。

而对于背包容量小于环的，如果跑完背包后刚好装满，那么贡献就是背包容量，否则就是背包容量$-1$，因为我们可以把剩下的环拆成链，这样只有一条链，负面贡献为$1$。

由于这个物品实际上是会重复的，并且至多只会有$\sqrt{m}$ 种，如果单纯跑$01$背包复杂度将会在$O(nm)$。

因此我们，需要统计种类，然后使用二进制优化，或者单调队列优化来优化这个多重背包，使用单调队列优化复杂度在$O(\sqrt{m}\ast n)$。当然二进制优化也能过 ，并且这题种类不会很多，使用二进制优化跑的更快。

代码（二进制优化）

//solve函数
const int N = 2e5 + 10;int fa[N], siz[N];
inline int find(int x) {return fa[x] = fa[x] == x ? x : find(fa[x]);
}void solve() {int n, m;std::cin >> n >> m;for (int i = 1; i <= m; i++) {siz[i] = 1;fa[i] = i;}std::vector<bool> cyc(m);for (int i = 1; i <= n; i++) {int u, v;std::cin >> u >> v;int a = find(u), b = find(v);if (a == b) {cyc[a] = true;}else {fa[b] = a;siz[a] += siz[b];}}int sum = 0;std::map<pii, int>mp;std::vector<int>b;for (int i = 1; i <= m; ++i) {if (fa[i] == i) {if (cyc[i]) {mp[{siz[i], siz[i]}]++;sum += siz[i];}else {b.push_back(siz[i] - 1);}}}std::vector<int>f(n + 1);std::vector<int>aa, bb;for (auto& [t, z] : mp) {auto [y, x] = t;for (int k = 0; k < 32; ++k) {if (z - (1LL << k) <= 0) break;aa.push_back((1LL << k) * y);bb.push_back((1LL << k) * x);z -= 1LL << k;}if (z) {aa.push_back(z * y);bb.push_back(z * x);}}for (int i = 0; i < bb.size(); ++i) {for (int j = n; j >= aa[i]; --j) {f[j] = std::max(f[j], f[j - aa[i]] + bb[i]);}}std::sort(b.begin(), b.end(), std::greater<>());int j = 0;std::vector<int>res(n + 1);int s = sum;for (int i = 1; i <= n; ++i) {if (i <= s) {res[i] = i - !(f[i] == i);}else {while (i > sum) sum += b[j++];res[i] = i - j;}}for (int i = 1; i <= n; ++i) {std::cout << res[i] << " ";}std::cout << "\n";
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//std::cin >> t;while (t--) {solve();}
}

代码（单调队列优化）

const int N = 2e5 + 10;int fa[N], siz[N];
int q[N];
inline int find(int x) {return fa[x] = fa[x] == x ? x : find(fa[x]);
}void solve() {int n, m;std::cin >> n >> m;for (int i = 1; i <= m; i++) {siz[i] = 1;fa[i] = i;}std::vector<bool> cyc(m);for (int i = 1; i <= n; i++){int u, v;std::cin >> u >> v;int a = find(u), b = find(v);if (a == b) {cyc[a] = true;}else {fa[b] = a;siz[a] += siz[b];}}int sum = 0;std::map<pii, int>mp;std::vector<int>b;for (int i = 1; i <= m ; ++i) {if (fa[i] == i) {if (cyc[i]) {mp[{siz[i], siz[i]}]++;sum += siz[i];}else {b.push_back(siz[i] - 1);}}}std::vector<int>f(n + 1);for (auto& [x, s] : mp) {auto g = f;auto [v, w] = x;for (int j = 0; j < v; ++j) {int h = 0, t = -1;for (int k = j; k <= n; k += v) {while (h <= t && q[h] < k - s * v) {h++;}if (h <= t) {f[k] = std::max(g[k], g[q[h]] + (k - q[h]) / v * w);}while (h <= t && g[k] >= g[q[t]] + (k - q[t]) / v * w) {t--;}q[++t] = k;}}}std::sort(b.begin(), b.end(), std::greater<>());int j = 0;std::vector<int>res(n + 1);int s = sum;for (int i = 1; i <= n; ++i) {if (i <= s) {res[i] = i - !(f[i]==i);}else {while (i > sum) sum += b[j++];res[i] = i - j;}}for (int i = 1; i <= n; ++i) {std::cout << res[i] << " ";}std::cout << "\n";
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//std::cin >> t;while (t--) {solve();}
};