#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
struct R {
int a, b, c, lca;
};
vector<int> t[5001];
vector<R> r;
pair<int, int> p[5001];
bool e[5001];
int dp[5001][1 << 10], tm = 0, tin[5001], tout[5001], deg[5001];
bool operator<(R A, R B) {
return tout[A.lca] < tout[B.lca];
}
void d(int node = 1, int parent = 0) {
e[node] = !e[parent];
tin[node] = ++tm;
for (int i : t[node]) {
if (i != parent) {
p[i] = {node, 1 << deg[node]++};
d(i, node);
}
}
tout[node] = ++tm;
}
bool par(int A, int B) {
return tin[A] <= tin[B] && tout[A] >= tout[B];
}
int lca(int A, int B) {
while (!par(A, B)) A = p[A].first;
return A;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, cost = 0;
cin >> n >> m;
FOR(i, 0, m) {
int a, b, c;
cin >> a >> b >> c;
cost += c;
if (!c) {
t[a].push_back(b);
t[b].push_back(a);
}
r.push_back({a, b, c});
}
d();
FOR(i, 0, m) r[i].lca = lca(r[i].a, r[i].b);
sort(r.begin(), r.end());
for (R i : r) {
if (i.c && e[i.a] ^ e[i.b]) continue;
int sm = i.c;
pair<int, int> A, B;
for (A = {i.a, 0}; A.first != i.lca; A = p[A.first]) sm += dp[A.first][A.second];
for (B = {i.b, 0}; B.first != i.lca; B = p[B.first]) sm += dp[B.first][B.second];
for (int mask = (1 << deg[i.lca]) - 1; ~mask; mask--) {
if (!(mask & A.second || mask & B.second)) {
dp[i.lca][mask] = max(dp[i.lca][mask], sm + dp[i.lca][mask | A.second | B.second]);
}
}
}
cout << cost - dp[1][0];
return 0;
}
Compilation message
training.cpp: In function 'void d(int, int)':
training.cpp:21:19: error: reference to 'tm' is ambiguous
tin[node] = ++tm;
^~
training.cpp:13:24: note: candidates are: int tm
int dp[5001][1 << 10], tm = 0, tin[5001], tout[5001], deg[5001];
^~
In file included from /usr/include/c++/7/ctime:42:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:49,
from training.cpp:1:
/usr/include/time.h:133:8: note: struct tm
struct tm
^~
training.cpp:28:20: error: reference to 'tm' is ambiguous
tout[node] = ++tm;
^~
training.cpp:13:24: note: candidates are: int tm
int dp[5001][1 << 10], tm = 0, tin[5001], tout[5001], deg[5001];
^~
In file included from /usr/include/c++/7/ctime:42:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:49,
from training.cpp:1:
/usr/include/time.h:133:8: note: struct tm
struct tm
^~
