Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Every edge weight is paid at least once, because every edge must be marked. So write the answer as plus the minimum extra cost needed to move between the trails.
If you add every transfer as a fake edge, the whole trip becomes an Euler tour. That means the fake edges only need to fix parity: the vertices with odd original degree must be paired up.
For edge index , look at the connected component after adding edges . Because transfer paths may be non-simple, edge lets you transfer between any two distinct vertices in that whole component for cost .
Those components form a laminar family: two of them are either disjoint or one contains the other. This makes the transfer costs ultrametric-ish, so greedy pairing by increasing transfer cost is valid.
Build the DSU union tree by edge index. Each edge event corresponds to a subtree interval. Sort events by ; inside that interval, pair all currently-unmatched odd vertices except possibly one. That is the whole algorithm.
We first separate the part of the cost that is completely unavoidable.
Every edge must be marked at least once, and marking edge costs . So every answer contains
The only interesting part is the extra movement needed when the marked edges cannot be traversed as one closed Euler tour.
Imagine every transfer as a fake edge between its start and end vertices, with cost equal to the transfer cost. If we mark every real edge exactly once and use some fake edges, then the whole journey is just a closed walk in this mixed graph.
A closed walk uses every vertex an even number of incident times. The original graph contributes its original degrees. Therefore the fake transfer edges must make exactly the odd-degree vertices even.
So the extra problem is:
Pair up all odd-degree vertices, minimizing the sum of transfer costs between paired vertices.
If there are no odd-degree vertices, we are already done: the original graph has an Euler tour starting and ending at vertex .
Self-loops are harmless here: they add to a degree, so they do not change parity.
This is the key weird bit. For an edge index , define as the connected component in the prefix graph using only edges that contains edge after it is added.
Then edge gives a transfer of cost between any two distinct vertices in .
Why? Suppose you want to transfer from to , both inside . You can walk through old prefix edges to reach one endpoint of edge , traverse edge , and then walk through old prefix edges to reach . If both vertices are on the same side of a bridge edge, just go across edge and back. The path is allowed to be non-simple, so yes, that nonsense is legal. The statement basically handed us a crowbar.
Conversely, if some transfer path has maximum edge index , then every vertex on that path lies inside . So all possible transfer options are exactly these complete-graph events:
For each edge , every pair of vertices inside can be connected for cost .
As edges are inserted by index, connected components only merge. So all sets form a laminar family: two such components are either disjoint, or one contains the other.
That gives a strong triangle-like property. If vertices can be transferred together using component , and using component , then and overlap at . Since the family is laminar, one contains the other, so the larger component also contains and . Thus going through intermediate vertices never beats directly pairing odd vertices. We only need a minimum perfect matching on the odd vertices under these laminar clique costs.
Now process all edge events in increasing order of .
When we process component with cost , look at how many currently-unmatched odd vertices are inside it. Say there are .
Pair pairs right now, paying for each, and leave one unmatched only if is odd.
Why is this safe? At this moment, no future event is cheaper. If two unmatched vertices inside are both eventually sent outside instead, those two outside partners can be re-paired using the laminar triangle property, while the two inside vertices pair now for . Since all involved future costs are at least , this exchange never increases the answer. So all but possibly one vertex in the component should be settled immediately.
The identity of the survivor does not matter. Future components that connect this component to the outside contain the whole component, not some special chosen vertex.
We need to process components quickly.
Build a DSU union tree by edge index:
After this, every event component is a subtree in the union tree. Run an Euler tour; each event becomes an interval over original vertices.
Mark all odd-degree vertices as active at their Euler positions. Sort edge events by weight. For each event interval, scan active positions inside it, delete them two at a time, and add the current edge weight per deleted pair. A small DSU-next array over Euler positions lets us jump to the next still-active odd vertex and delete positions in near-linear time.
Total complexity is
with linear memory. The sort is the main cost; everything else is basically chill.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
int maxNodes = 2 * n + 5;
vector<int> parent(maxNodes), lc(maxNodes), rc(maxNodes), tin(maxNodes), tout(maxNodes);
vector<char> odd(n + 1, 0);
for (int i = 1; i <= n; i++) parent[i] = i;
auto findRoot = [&](int x) {
int r = x;
while (parent[r] != r) r = parent[r];
while (parent[x] != x) {
int y = parent[x];
parent[x] = r;
x = y;
}
return r;
};
vector<ll> w(m);
vector<int> eventNode(m), order(m);
ll ans = 0;
int tot = n;
for (int i = 0; i < m; i++) {
int u, v;
ll ww;
cin >> u >> v >> ww;
w[i] = ww;
ans += ww;
if (u != v) {
odd[u] ^= 1;
odd[v] ^= 1;
}
int ru = findRoot(u), rv = findRoot(v);
if (ru != rv) {
++tot;
lc[tot] = ru;
rc[tot] = rv;
parent[tot] = tot;
parent[ru] = tot;
parent[rv] = tot;
eventNode[i] = tot;
} else {
eventNode[i] = ru;
}
}
int root = findRoot(1);
int timer = 0;
vector<pair<int, int>> st;
st.push_back({root, 0});
while (!st.empty()) {
auto [v, state] = st.back();
st.pop_back();
if (v <= n) {
tin[v] = tout[v] = ++timer;
} else if (state == 0) {
st.push_back({v, 1});
st.push_back({rc[v], 0});
st.push_back({lc[v], 0});
} else {
tin[v] = min(tin[lc[v]], tin[rc[v]]);
tout[v] = max(tout[lc[v]], tout[rc[v]]);
}
}
vector<char> active(n + 2, 0);
int remaining = 0;
for (int v = 1; v <= n; v++) {
if (odd[v]) {
active[tin[v]] = 1;
remaining++;
}
}
vector<int> nxt(n + 2);
nxt[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
nxt[i] = active[i] ? i : nxt[i + 1];
}
auto nextActive = [&](int x) {
if (x > n) return n + 1;
int r = x;
while (nxt[r] != r) r = nxt[r];
while (nxt[x] != x) {
int y = nxt[x];
nxt[x] = r;
x = y;
}
return r;
};
auto eraseActive = [&](int x) {
nxt[x] = nextActive(x + 1);
};
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
return w[a] < w[b];
});
for (int id : order) {
if (remaining == 0) break;
int node = eventNode[id];
int L = tin[node], R = tout[node];
int p = nextActive(L);
int pending = 0;
while (p <= R) {
if (pending == 0) {
pending = p;
p = nextActive(p + 1);
} else {
int q = p;
eraseActive(pending);
eraseActive(q);
ans += w[id];
remaining -= 2;
pending = 0;
if (remaining == 0) break;
p = nextActive(q + 1);
}
}
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
int maxNodes = 2 * n + 5;
vector<int> parent(maxNodes), lc(maxNodes), rc(maxNodes), tin(maxNodes), tout(maxNodes);
vector<char> odd(n + 1, 0);
for (int i = 1; i <= n; i++) parent[i] = i;
auto findRoot = [&](int x) {
int r = x;
while (parent[r] != r) r = parent[r];
while (parent[x] != x) {
int y = parent[x];
parent[x] = r;
x = y;
}
return r;
};
vector<ll> w(m);
vector<int> eventNode(m), order(m);
ll ans = 0;
int tot = n;
for (int i = 0; i < m; i++) {
int u, v;
ll ww;
cin >> u >> v >> ww;
w[i] = ww;
ans += ww;
if (u != v) {
odd[u] ^= 1;
odd[v] ^= 1;
}
int ru = findRoot(u), rv = findRoot(v);
if (ru != rv) {
++tot;
lc[tot] = ru;
rc[tot] = rv;
parent[tot] = tot;
parent[ru] = tot;
parent[rv] = tot;
eventNode[i] = tot;
} else {
eventNode[i] = ru;
}
}
int root = findRoot(1);
int timer = 0;
vector<pair<int, int>> st;
st.push_back({root, 0});
while (!st.empty()) {
auto [v, state] = st.back();
st.pop_back();
if (v <= n) {
tin[v] = tout[v] = ++timer;
} else if (state == 0) {
st.push_back({v, 1});
st.push_back({rc[v], 0});
st.push_back({lc[v], 0});
} else {
tin[v] = min(tin[lc[v]], tin[rc[v]]);
tout[v] = max(tout[lc[v]], tout[rc[v]]);
}
}
vector<char> active(n + 2, 0);
int remaining = 0;
for (int v = 1; v <= n; v++) {
if (odd[v]) {
active[tin[v]] = 1;
remaining++;
}
}
vector<int> nxt(n + 2);
nxt[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
nxt[i] = active[i] ? i : nxt[i + 1];
}
auto nextActive = [&](int x) {
if (x > n) return n + 1;
int r = x;
while (nxt[r] != r) r = nxt[r];
while (nxt[x] != x) {
int y = nxt[x];
nxt[x] = r;
x = y;
}
return r;
};
auto eraseActive = [&](int x) {
nxt[x] = nextActive(x + 1);
};
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
return w[a] < w[b];
});
for (int id : order) {
if (remaining == 0) break;
int node = eventNode[id];
int L = tin[node], R = tout[node];
int p = nextActive(L);
int pending = 0;
while (p <= R) {
if (pending == 0) {
pending = p;
p = nextActive(p + 1);
} else {
int q = p;
eraseActive(pending);
eraseActive(q);
ans += w[id];
remaining -= 2;
pending = 0;
if (remaining == 0) break;
p = nextActive(q + 1);
}
}
}
cout << ans << '\n';
}
}