#include <bits/stdc++.h>
using namespace std;
struct edge {
int a, b, c, lca;
};
vector<edge> edges, fe;
int total = 0;
vector<int> adj[1005];
int tin[1005], timer = 1;
int jmp[1005][12], depth[1005];
int col[1005];
pair<int, int> par[1005];
int deg[1005];
int dp[1005][1 << 11];
void dfs(int node) {
tin[node] = timer++;
for (int i = 1; i < 12; i++) jmp[node][i] = jmp[jmp[node][i-1]][i-i];
for (auto nxt : adj[node]) {
if (tin[nxt]) continue;
if (col[node] == 1) col[nxt] = 2;
else col[nxt] = 1;
par[nxt] = {node, (1 << deg[node]++)};
depth[nxt] = depth[node] + 1;
jmp[nxt][0] = node;
dfs(nxt);
}
}
int lca(int a, int b) {
if (depth[a] > depth[b]) swap(a, b);
for (int i = 11; i >= 0; i--) if (depth[jmp[b][i]] >= depth[a]) b = jmp[b][i];
if (a == b) return a;
for (int i = 11; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) a = jmp[a][i]; b = jmp[b][i];
return jmp[a][0];
}
int main() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
total += c;
if (c == 0) adj[a].push_back(b); adj[b].push_back(a);
edges.push_back({a, b, c});
}
col[1] = 1;
jmp[1][0] = 1;
depth[1] = 1;
dfs(1);
for (auto e: edges) {
if (col[e.a] == col[e.b]) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
else if (e.c == 0) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
}
sort(fe.begin(), fe.end(), [&](edge a, edge b) {
return tin[a.lca] > tin[b.lca];
});
for (auto e : fe) {
int tot = e.c;
int finalmask = 0;
int mask = 0;
for (int i = e.a; i != e.lca; mask = par[i].second, i = par[i].first) tot += dp[i][mask];
finalmask |= mask;
mask = 0;
for (int i = e.b; i != e.lca;mask = par[i].second, i = par[i].first) tot += dp[i][mask];
finalmask |= mask;
for (int mk = (1 << deg[e.lca]) - 1; mk >= 0 ; mk--) {
if (mk & finalmask) continue;
dp[e.lca][mk] = max(dp[e.lca][mk], dp[e.lca][mk | finalmask] + tot);
}
}
cout << total - dp[1][0];
}
Compilation message
training.cpp: In function 'int lca(int, int)':
training.cpp:38:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
38 | for (int i = 11; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) a = jmp[a][i]; b = jmp[b][i];
| ^~~
training.cpp:38:78: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
38 | for (int i = 11; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) a = jmp[a][i]; b = jmp[b][i];
| ^
training.cpp:38:89: error: 'i' was not declared in this scope
38 | for (int i = 11; i >= 0; i--) if (jmp[a][i] != jmp[b][i]) a = jmp[a][i]; b = jmp[b][i];
| ^
training.cpp: In function 'int main()':
training.cpp:48:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
48 | if (c == 0) adj[a].push_back(b); adj[b].push_back(a);
| ^~
training.cpp:48:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
48 | if (c == 0) adj[a].push_back(b); adj[b].push_back(a);
| ^~~
