题意
给出 \(n\) 个点，\(k\) 条未钦定边权的边和 \(m\) 条已钦定边权的边，要求为这 \(k\) 条未指定边权的边分配权值使其均在图的最小生成树中且最大化这 \(k\) 条边的边权之和。
（\(1 \le n,k,m \le 5 \times 10^5\)）。
题解
首先满足要求这 \(k\) 条边均在最小生成树中，考虑将这 \(k\) 条边的权值置为极小值后建立最小生成树。然后考虑最大化边权之和。
此时需要考虑的是非树边对树边边权的限制，若有一条非树边 \(\left(a, b\right)\)，边权为 \(w\)，那么可以得出在最小生成树上的路径 \(a \rightarrow b\) 上的边边权均要满足不大于 \(w\)，否则其将被非树边 \(\left(a, b\right)\) 替代。
发现这一过程为树链取最小值，使用树链剖分即可。如果存在未指定边权的边在处理完所有限制后没有限制到，输出 \(-1\) 即可。在 \(n,m,k\) 同阶的情况下总复杂度为 \(\mathcal{O}(n \log^2 n)\)，可以通过本题。
Code
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
constexpr valueType MAX = INT_MAX >> 1;
class DSU {
private:
valueType N;
std::vector<int> father, size;
public:
explicit DSU(valueType n) : N(n), father(N, 0), size(N, 0) {
std::iota(father.begin(), father.end(), 0);
std::fill(size.begin(), size.end(), 1);
}
void resize(valueType n) {
N = n;
father.resize(N, 0);
size.resize(N);
std::iota(father.begin(), father.end(), 0);
std::fill(size.begin(), size.end(), 1);
}
int find(int x) {
return father[x] == x ? x : father[x] = find(father[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (size[x] < size[y]) std::swap(x, y);
father[y] = x;
size[x] += size[y];
}
bool connected(int x, int y) {
return find(x) == find(y);
}
valueType count(valueType n) {
return size[find(n)];
}
};
class Tree {
public:
typedef ValueVector container;
private:
valueType N;
container data;
void push(valueType id) {
if (data[id] != MAX) {
data[id << 1] = std::min(data[id << 1], data[id]);
data[id << 1 | 1] = std::min(data[id << 1 | 1], data[id]);
data[id] = MAX;
}
}
public:
explicit Tree(valueType n) : N(n), data((N << 2) + 10, MAX) {}
void resize(valueType n) {
N = n;
data.resize((N << 2) + 10, MAX);
}
void update(valueType l, valueType r, valueType key) {
if (l > r)
return;
update(1, 1, N, l, r, key);
}
container ans() {
container result(N + 1, MAX);
query(1, 1, N, result);
return result;
}
private:
void update(valueType id, valueType nodeL, valueType nodeR, valueType queryL, valueType queryR, valueType key) {
if (queryL <= nodeL && nodeR <= queryR) {
data[id] = std::min(data[id], key);
return;
}
valueType const mid = (nodeL + nodeR) >> 1;
push(id);
if (queryL <= mid)
update(id << 1, nodeL, mid, queryL, queryR, key);
if (queryR > mid)
update(id << 1 | 1, mid + 1, nodeR, queryL, queryR, key);
}
void query(valueType id, valueType l, valueType r, container &result) {
if (l == r) {
result[l] = data[id];
return;
}
valueType const mid = (l + r) >> 1;
push(id);
query(id << 1, l, mid, result);
query(id << 1 | 1, mid + 1, r, result);
}
};
struct Edge {
valueType from, to, weight;
bool tag;
Edge(valueType from, valueType to, valueType weight, bool tag) : from(from), to(to), weight(weight), tag(tag) {}
bool operator<(Edge const &obj) const {
return weight < obj.weight;
}
};
typedef std::vector<Edge> EdgeVector;
valueType N, K, M;
ValueVector dfn, father, depth, size, son, top;
ValueMatrix G;
Tree tree(N + 1);
void dfs(valueType x, valueType from) {
father[x] = from;
depth[x] = depth[from] + 1;
size[x] = 1;
for (auto const &iter: G[x]) {
if (iter == from)
continue;
dfs(iter, x);
size[x] += size[iter];
if (son[x] == 0 || size[iter] > size[son[x]])
son[x] = iter;
}
}
valueType dfsCount = 0;
void build(valueType x, valueType from, valueType TOP) {
dfn[x] = ++dfsCount;
top[x] = TOP;
if (son[x] == 0)
return;
build(son[x], x, TOP);
for (auto const &iter: G[x]) {
if (iter == from || iter == son[x])
continue;
build(iter, x, iter);
}
}
void modify(valueType x, valueType y, valueType key) {
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]])
std::swap(x, y);
tree.update(dfn[top[x]], dfn[x], key);
x = father[top[x]];
}
if (depth[x] > depth[y])
std::swap(x, y);
tree.update(dfn[x] + 1, dfn[y], key);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
//#ifndef LOCAL_STDIO
// freopen("trade.in", "r", stdin);
// freopen("trade.out", "w", stdout);
//#endif
std::cin >> N >> K >> M;
G.resize(N + 1);
dfn.resize(N + 1);
father.resize(N + 1);
depth.resize(N + 1);
size.resize(N + 1);
son.resize(N + 1);
top.resize(N + 1);
tree.resize(N + 1);
EdgeVector edge;
edge.reserve(K + M);
for (valueType i = 0; i < K; ++i) {
valueType u, v;
std::cin >> u >> v;
edge.emplace_back(u, v, 0, true);
}
for (valueType i = 0; i < M; ++i) {
valueType u, v, w;
std::cin >> u >> v >> w;
edge.emplace_back(u, v, w, false);
}
std::sort(edge.begin() + K, edge.end());
EdgeVector treeEdge, remainEdge;
treeEdge.reserve(N);
remainEdge.reserve(K + M);
DSU dsu(N + 1);
for (auto const &iter: edge) {
if (dsu.connected(iter.from, iter.to)) {
remainEdge.push_back(iter);
} else {
dsu.unite(iter.from, iter.to);
treeEdge.push_back(iter);
G[iter.from].emplace_back(iter.to);
G[iter.to].emplace_back(iter.from);
}
}
ValueVector root;
for (valueType i = 1; i <= N; ++i) {
if (dfn[i] == 0) {
dfs(i, 0);
build(i, 0, i);
root.push_back(i);
}
}
for (auto const &iter: root)
tree.update(dfn[iter], dfn[iter], 0);
for (auto &iter: treeEdge) {
if (!iter.tag) {
if (depth[iter.from] > depth[iter.to])
std::swap(iter.from, iter.to);
tree.update(dfn[iter.to], dfn[iter.to], 0);
}
}
for (auto const &iter: remainEdge) {
modify(iter.from, iter.to, iter.weight);
}
auto const &result = tree.ans();
long long ans = 0;
for (valueType i = 1; i <= N; ++i) {
if (result[dfn[i]] == MAX) {
std::cout << -1 << std::endl;
std::exit(0);
}
ans += result[dfn[i]];
}
std::cout << ans << std::endl;
std::exit(0);
}