T1. 社團(tuán)招新
\(20\) 分：\((n \leqslant 10)\)
直接用 dfs 暴力枚舉每個(gè)人加入分配到哪一個(gè)社團(tuán)中。在 dfs 的過程中維護(hù)當(dāng)前已經(jīng)得到總評(píng)分 \(sum\)，以及當(dāng)前每個(gè)社團(tuán)的人數(shù) \(c_1, c_2, c_3\) 。當(dāng)找到一種分配方式后，判斷 \(\max(c_1, c_2, c_3)\) 是否不超過 \(\frac{n}{2}\) 并用 \(sum\) 更新答案即可。時(shí)間復(fù)雜度為 \(O(3^n)\) 。
另外 \(35\) 分：\((n \leqslant 200)\)
不難發(fā)現(xiàn)上述 dfs 的過程中，存在大量重復(fù)的子問題，考慮用動(dòng)態(tài)規(guī)劃進(jìn)行優(yōu)化。
設(shè) f[i][j][k] 表示當(dāng)前分配了前 \(i\) 人，且 \(c_1 = j\)，\(c_2 = k\)，\(c_3 = i-j-k\) 時(shí)，能夠得到的最大評(píng)分總和。
枚舉 \(i, j, k\)，然后分別考慮當(dāng)前的第 \(i\) 人分配到哪個(gè)社團(tuán)，可以得到轉(zhuǎn)移方程：
求最終的答案時(shí)，枚舉兩個(gè)社團(tuán)的人數(shù) \(j, k\)，然后判斷三個(gè)社團(tuán)是否都不超過 \(\frac{n}{2}\) 人，取滿足這個(gè)條件的最大 \(f[n][j][k]\) 即可，時(shí)間復(fù)雜度為 \(O(n^3)\) 。
另外 \(5\) 分：(特殊性質(zhì) \(A\))
此時(shí) \(a_{i,2}=a_{i,3}=0\)，相當(dāng)于僅有一個(gè)社團(tuán)，直接取最大的 \(\frac{n}{2}\) 個(gè) \(a_{i,1}\) 相加即可。
另外 \(10\) 分：（特殊性質(zhì) \(B\)）
此時(shí) \(a_{i,3} = 0\)，相當(dāng)于僅有兩個(gè)社團(tuán)，若不考慮“人數(shù)不超過 \(\frac{n}{2}\)” 的限制，那么答案就是 \(\max(a_{i,1}, a_{i, 2})\) 之和，即每個(gè)人取最大的社團(tuán)評(píng)分相加。在此基礎(chǔ)上考慮限制，設(shè) \(c_1, c_2\) 為不考慮限制時(shí)兩個(gè)社團(tuán)的人數(shù)，那么：
- 若 \(c_1 = c_2\)，則此時(shí)兩個(gè)社團(tuán)人數(shù)都是 \(\frac{n}{2}\) 無需做出任何改變。
- 若 \(c_1 > c_2\)，則需要將第一個(gè)社團(tuán)中的 \(c_1 - \frac{n}{2}\) 個(gè)人分配到第二個(gè)，已知每個(gè)人從第一個(gè)社團(tuán)轉(zhuǎn)移到第二個(gè)社團(tuán)后，產(chǎn)生的貢獻(xiàn)是 \(a_{i,2}-a_{i,1}\)，那么取前 \(c_1 - \frac{n}{2}\) 大的貢獻(xiàn)相加即可。
- 若 \(c_1 < c_2\)，則處理方式與 \(c_1 > c_2\) 類似。
可以使用優(yōu)先隊(duì)列或是 sort 排序來得到前幾大的貢獻(xiàn)，時(shí)間復(fù)雜度為 \(O(n\log n)\) 。
另外 \(10\) 分：（特殊性質(zhì) \(C\)）
此時(shí)的 \(a_{i, j}\) 是隨機(jī)生成的，那么對(duì)于第 \(j(j \in \{1, 2, 3\})\) 個(gè)社團(tuán)而言，\(a_{i, j}\) 是三個(gè)社團(tuán)評(píng)分中最大的概率約 \(\frac{1}{3}\) 。也就是說，如果我們直接對(duì)每個(gè)人取 \(\max(a_{i, j})\) 相加，那么最終每個(gè)社團(tuán)的人數(shù)約等于 \(\frac{n}{3} \leqslant \frac{n}{2}\)，必然滿足題目的人數(shù)限制。時(shí)間復(fù)雜度為 \(O(n)\) 。
\(100\) 分：
考慮在“特殊性質(zhì) \(B\)”的基礎(chǔ)上進(jìn)行優(yōu)化，依舊是先將每個(gè)人最大的社團(tuán)評(píng)分相加。設(shè) \(p\) 表示人數(shù)最多的社團(tuán)編號(hào)，那么：
- 若 \(c_p \leqslant \frac{n}{2}\)，則另外兩個(gè)社團(tuán)人數(shù)肯定也都 \(\leqslant \frac{n}{2}\)，直接輸出答案。
- 若 \(c_p > \frac{n}{2}\)，則此時(shí)我們需要從第 \(p\) 個(gè)社團(tuán)中選出 \(c_p - \frac{n}{2}\) 個(gè)人移動(dòng)到其他社團(tuán)。根據(jù)貪心的思想，為了讓答案減得更少，需要將這些人移動(dòng)到他們?cè)?strong>次大評(píng)分的社團(tuán)中。移動(dòng)后，\(c_p = \frac{n}{2}\) 且另外兩個(gè)社團(tuán)的人數(shù)總和 \(= \frac{n}{2}\)，那么也就是說三個(gè)社團(tuán)的人數(shù)都是 \(\leqslant \frac{n}{2}\) 的，符合人數(shù)限制。
至此，我們便可以像之前一樣，用優(yōu)先隊(duì)列或者 sort 排序來得到前 \(c_p - \frac{n}{2}\) 大的“次大減最大”的貢獻(xiàn)，加到答案中即可，時(shí)間復(fù)雜度依然是 \(O(n\log n)\) 。
值得一提的是由于每個(gè)人只會(huì)選擇前兩大的社團(tuán)，因此本題還可以做更多個(gè)社團(tuán)的情況。
代碼實(shí)現(xiàn)
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
void solve() {
int n;
cin >> n;
vector a(n, vector<int>(3));
rep(i, n)rep(j, 3) cin >> a[i][j];
int ans = 0;
vector<int> cnt(3); int p = 0;
vector<int> mx(n), mx2(n), js(n);
rep(i, n) {
rep(j, 3) {
int x = a[i][j];
if (mx[i] < x) {
mx2[i] = mx[i];
mx[i] = x;
js[i] = j;
}
else {
mx2[i] = max(mx2[i], x);
}
}
ans += mx[i];
++cnt[js[i]];
if (cnt[js[i]] > cnt[p]) p = js[i];
}
if (cnt[p] <= n/2) {
cout << ans << '\n';
return;
}
priority_queue<int> q;
rep(i, n) {
if (js[i] != p) continue;
q.push(mx2[i]-mx[i]);
}
int k = cnt[p]-n/2;
while (k--) {
ans += q.top();
q.pop();
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
T2. 道路修復(fù)
\(16\) 分：\((k \leqslant 0)\)
此時(shí) \(k \leqslant 0\)，不需要考慮鄉(xiāng)鎮(zhèn)對(duì)城市帶來的影響。因此可以直接使用 \(\text{Kruskal}\) 算法來計(jì)算出最小生成樹的邊權(quán)總和即可。具體地，將 \(m\) 條邊按照邊權(quán)從小到大排序，然后依次考慮連接每一條邊后是否會(huì)形成環(huán)。若不形成環(huán)，則加入這條邊否則不加入。判斷是否形成環(huán)，可以使用并查集。時(shí)間復(fù)雜度為 \(O(m\log m)\) 。
另外 \(32\) 分：（特殊性質(zhì) \(A\)）
此時(shí) \(c_j = 0\)，且對(duì)于每個(gè)鄉(xiāng)鎮(zhèn) \(j\)，都存在一個(gè)城市 \(i\) 滿足 \(a_{j, i} = 0\) 。這說明任何一個(gè)鄉(xiāng)鎮(zhèn)都可以通過一個(gè)邊權(quán)為 \(0\) 的邊加入到一個(gè)已經(jīng)連通的圖中，即需要付出的代價(jià)是 \(0\) 。而如果是中途將鄉(xiāng)鎮(zhèn)與未連通圖中的某個(gè)連通塊進(jìn)行連接（前提是這個(gè)連通塊中存在鄉(xiāng)鎮(zhèn)邊權(quán)為 \(0\) 的城市），然后再通過城市之間的邊將每個(gè)城市進(jìn)行連通，那么仍然能夠發(fā)現(xiàn)使所有鄉(xiāng)鎮(zhèn)與城市連通需要的代價(jià)還是 \(0\) 。
容易得到一個(gè)貪心的想法：既然任何一個(gè)時(shí)刻將鄉(xiāng)鎮(zhèn)與城市進(jìn)行連通，那么不妨一開始就讓所有鄉(xiāng)鎮(zhèn)與它對(duì)應(yīng)的 \(0\) 代價(jià)城市相連接。這樣一來，就可以在一開始不費(fèi)任何代價(jià)地產(chǎn)生盡可能多的邊權(quán)更小的邊，這些邊都是鄉(xiāng)鎮(zhèn)與城市之間的邊，用于原圖中的城市相互之間進(jìn)行連接。具體地，對(duì)于鄉(xiāng)鎮(zhèn) \(j\) 進(jìn)行如下額外的連邊：
- 令鄉(xiāng)鎮(zhèn)的編號(hào)為 \(n+j\)，城市的編號(hào)為 \(i(1 \leqslant i \leqslant n)\) ；
- 那么在 \(n+j\) 與 \(i\) 之間連接一條邊權(quán)為 \(a_{j, i}\) 的邊。
隨后，將這些額外的邊與原本城市之間的邊一同排序，進(jìn)行一次 \(\text{Kruskal}\) 算法即可計(jì)算出答案，注意使用 long long 。設(shè)考慮到 \(m \geqslant nk\)，且 \(n > k\)，時(shí)間復(fù)雜度依然是 \(O(m\log m)\) 。
另外 \(24\) 分：\((k \leqslant 5)\)
注意到 \(k \leqslant 5\) 很小，可以考慮 \(\text{dfs}\) 枚舉每個(gè)城鎮(zhèn)是否使用。具體的做法與上述“特殊性質(zhì) \(A\)” 的做法類似，對(duì)于枚舉到的每一種使用鄉(xiāng)鎮(zhèn)的情況，只需要把用到的鄉(xiāng)鎮(zhèn)對(duì)應(yīng)的邊額外加入進(jìn)來即可，以便產(chǎn)生值更小的邊用于城市之間的連通。\(\text{dfs}\) 部分的復(fù)雜度是 \(O(2^k)\)，總時(shí)間復(fù)雜度是 \(O(2^km\log m)\) 。
\(100\) 分：
復(fù)雜度的瓶頸在于每次都將 \(m\) 條邊重新排序了，需要考慮將 \(O(m\log m)\) 的排序從 \(2^k\) 中提取出來。不難發(fā)現(xiàn)，\(m \leqslant 10^6\) 雖然很大，但是 \(n \leqslant 10^4\) 比較小，能夠構(gòu)成生成樹的邊至多有 \(O(n)\) 條。于是我們可以先對(duì)城市之間的 \(m\) 條邊進(jìn)行一次 \(\text{Kruskal}\)，提取出其中有用的 \(n-1\) 條樹邊。
這樣一來，對(duì)于 \(\text{dfs}\) 枚舉到的每一種鄉(xiāng)鎮(zhèn)情況，總邊數(shù)就是 \(O(nk)\) 級(jí)別而非 \(O(m+nk)\)，時(shí)間復(fù)雜度優(yōu)化到了 \(O(m\log m + 2^knk\log (nk))\)。然而，這樣的復(fù)雜度可能還不足以通過本題。
考慮到每次還是會(huì)對(duì)邊重新排序，為了避免這種情況，我們其實(shí)完全可以在 \(\text{dfs}\) 之前，提前將所有的 \(nk\) 條邊與 \(n-1\) 條樹邊放在一起排序。為每條邊標(biāo)記上這條邊來自于哪一個(gè)城鎮(zhèn)，這樣一來，每次只需要枚舉 \(nk+n-1\) 條邊，根據(jù)邊的標(biāo)記來判斷對(duì)應(yīng)的鄉(xiāng)鎮(zhèn)當(dāng)前是否可以使用，進(jìn)而判斷當(dāng)前的這條邊是否可以選上。時(shí)間復(fù)雜度進(jìn)一步降到了 \(O(m\log m + 2^knk)\) 。
代碼實(shí)現(xiàn)
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
struct UnionFind {
vector<int> d;
UnionFind(int n = 0): d(n, -1) {}
int find(int x) {
if (d[x] < 0) return x;
return d[x] = find(d[x]);
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (d[x] > d[y]) swap(x, y);
d[x] += d[y];
d[y] = x;
return true;
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return -d[find(x)];
}
};
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, m, k;
cin >> n >> m >> k;
vector<tuple<int, int, int, int>> nes, es;
rep(i, m) {
int u, v, w;
cin >> u >> v >> w;
--u; --v;
nes.emplace_back(w, u, v, -1);
}
vector<int> c(k);
rep(j, k) {
cin >> c[j];
rep(i, n) {
int w;
cin >> w;
es.emplace_back(w, i, n+j, j);
}
}
sort(nes.begin(), nes.end());
UnionFind uf(n);
for (auto [w, u, v, _] : nes) {
if (!uf.unite(u, v)) continue;
es.emplace_back(w, u, v, -1);
}
sort(es.begin(), es.end());
ll ans = 1e18;
vector<bool> used(k);
auto Kruskal = [&]() {
ll res = 0;
rep(j, k) if (used[j]) res += c[j];
UnionFind uf2(n+k);
for (auto [w, u, v, id] : es) {
if (id != -1 and !used[id]) continue;
if (!uf2.unite(u, v)) continue;
res += w;
}
return res;
};
auto dfs = [&](auto& f, int i) -> void {
if (i == k) {
ans = min(ans, Kruskal());
return;
}
used[i] = true;
f(f, i+1);
used[i] = false;
f(f, i+1);
};
dfs(dfs, 0);
cout << ans << '\n';
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)