csp-s2025 T2
考场的时候把 $k<=10$ 看成 $k<=1e4$ 了，当时想了半天我说 CCF 怎么这次出的那么难呢，拿了个特殊性质 A 就跑了，你的这就算了吧，更可恶的是开二维数组 a[maxn][maxn]（maxn=1e4+5）直接 MLE 了，于是乎：$48pts$ -> $0pts$，造孽啊......
思路非常简单，就是坑多了一点其它还好
首先对于特殊性质 A 敲一遍 kruskal 模板直接过掉，不会的去【模板】最小生成树，预期 $48$ 分
注意到 $k<=10$，我们直接暴力二进制枚举，对于每一次枚举都跑一遍 kruskal，时间复杂度 $O(2^k \cdot (kn+m)\log(kn+m))$，预期 $48$ 分
发现此时 $2^k$ 是肯定无法再优化了，我们知道对于很多最小生成树的题目都是去想 kruskal 的算法原理，而且对于图论有一个非常经典的思路就是把时间复杂度从关于 $m$ 的转移到关于 $n$ 的，于是容易发现对于只考虑原本城市的图不需要一直排序，可以直接预处理出原本城市的图最小的前 $n-1$ 条边，并在 kruskal 函数中只考虑乡镇的边和 $n-1$ 条城市的边，时间复杂度 $O(m\log m + 2^k (kn)\log(kn))$，预期 $80$ 分（$n\log n$ 时间复杂度时 $n<=2e7$）
发现时限瓶颈卡在了排序给的 $\log$ 上，于是我们直接预处理排序，kruskal 函数里如果碰到不改造乡镇的边直接跳过即可，时间复杂度 $O(m\log m + kn\log kn + 2^k (kn))$，预期得分 $100$ 分
还有几个很坑的点：
- 务必要开
long long，否则 $100 \to 16$ - 务必要开快速读入，否则 $100 \to 96$
- 务必要开 $1e18$ 而不是
0x3f3f3f3f，否则 $100 \to 16$
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int n, m, k, c[maxn], a[15][maxn], ans = 1e18;
bool change[maxn];inline int r() {int x = 0, f = 1;char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0'); ch = getchar();}return f * x;
}struct Edge { int u, v, w; };
struct DSU {int fa[maxn];void init(int sz) {for (int i = 1; i <= sz; i++) fa[i] = i;}int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }bool merge(int x, int y) {x = find(x), y = find(y);if (x == y) return 0;fa[x] = y;return 1;}
}dsu;bool cmp(Edge x, Edge y) {if (x.w == y.w) return x.u < y.u;return x.w < y.w;
}int kruskal(vector<Edge> &edges) {int res = 0, num = 0;for (auto e : edges) {int u = e.u, v = e.v, w = e.w;if (v > n && !change[v - n]) continue;if (dsu.merge(u, v)) {res += w;num++;if (num >= n + k - 1) break;}}return res;
}signed main() {n = r(), m = r(), k = r();vector<Edge> olde;for (int i = 1; i <= m; i++) {int u = r(), v = r(), w = r();olde.push_back({u, v, w});}sort(olde.begin(), olde.end(), cmp);DSU dsu0;dsu0.init(n);int cnt = 0;vector<Edge> newe;for (auto e : olde) {if (dsu0.merge(e.u, e.v)) {newe.push_back(e);cnt++;if (cnt == n-1) break;}}vector<Edge> edges = newe; for (int i = 1; i <= k; i++) {c[i] = r();for (int j = 1; j <= n; j++) {a[i][j] = r();edges.push_back({j, n + i, a[i][j]});}}sort(edges.begin(), edges.end(), cmp);for (int i = 0; i < (1 << k); i++) {dsu.init(n + k); int cost = 0;for (int j = 0; j < k; j++) {change[j + 1] = (i >> j) & 1; cost += change[j + 1] * c[j + 1];}int mst_cost = kruskal(edges);ans = min(ans, mst_cost + cost);}cout << ans << endl;return 0;
}