#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+1, M = 5e3+1;
inline void setmax(int &a, int b) { if(b > a) a = b; }
int n, m, sum, upar[M], vpar[M];
vector<tuple<int,int,int> > unpaved;
vector<int> g[N], ls[N];
int d[N];
vector<int> anc[N];
void init_lca(int u, int par) {
for(int v: g[u]) if(v != par) {
d[v] = d[u] + 1;
anc[v].push_back(u);
for(int j = 0; 1 << j+1 <= d[v]; j++) anc[v].push_back(anc[anc[v][j]][j]);
init_lca(v, u);
}
}
int get_lca(int u, int v) {
if(d[u] < d[v]) swap(u, v);
for(int j = 0; d[u] > d[v]; j++) if(d[u] - d[v] >> j & 1) u = anc[u][j];
if(u == v) return u;
for(int j = 10; j >= 0; j--) if(j < anc[u].size() && anc[u][j] != anc[v][j])
u = anc[u][j], v = anc[v][j];
return anc[u][0];
}
int get_par(int u, int dist) {
for(int j = 0; 1 << j <= dist; j++) if(dist >> j & 1) u = anc[u][j];
return u;
}
int dp[N][N];
int rt1, rt2, val;
void rec_vals(int u, int par) {
setmax(dp[rt1][u], dp[rt2][u] + val);
for(int v: g[u]) if(v != par) rec_vals(v, u);
}
void dfs(int u, int par) {
vector<int> ord;
for(int v: g[u]) if(v != par) {
dfs(v, u);
ord.push_back(v);
}
vector<int> f(1 << ord.size());
map<int, int> rev;
for(int i = 0; i < ord.size(); i++) {
rev[ord[i]] = i;
setmax(f[1 << i], dp[ord[i]][ord[i]]);
}
for(int idx: ls[u]) {
int x, y, w; tie(x, y, w) = unpaved[idx];
// cout << u << ' ' << x << ' ' << y << ' ' << upar[idx] << ' ' << vpar[idx] << ' ' << w << endl;
if(y == u) {
setmax(f[(1 << rev[upar[idx]])], dp[upar[idx]][x] + w);
} else {
setmax(f[(1 << rev[upar[idx]]) | (1 << rev[vpar[idx]])], dp[upar[idx]][x] + dp[vpar[idx]][y] + w);
}
}
for(int mask = 1; mask < 1 << ord.size(); mask++) {
int lowbit = mask & -mask;
setmax(f[mask], f[mask ^ lowbit] + f[lowbit]);
if(!(mask ^ lowbit)) continue;
for(int i = 0; 1 << i < lowbit; i++) if(mask >> i & 1) {
setmax(f[mask], f[mask ^ lowbit ^ (1 << i)] + f[lowbit | (1 << i)]);
}
}
// cout << u << endl;
// for(int i = 0; i < 1 << ord.size(); i++) cout << i << ' ' << f[i] << endl;
rt1 = u;
for(int i = 0; i < ord.size(); i++) {
rt2 = ord[i];
val = f[((1 << ord.size()) - 1) ^ (1 << i)];
rec_vals(ord[i], u);
}
dp[u][u] = f[(1 << ord.size()) - 1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 0, u, v, w; i < m; i++) {
cin >> u >> v >> w;
if(!w) g[u].push_back(v), g[v].push_back(u);
else unpaved.emplace_back(u, v, w);
sum += w;
}
init_lca(1, 0);
vector<tuple<int,int,int> > tmp;
for(auto tt: unpaved) {
int u, v, w;
tie(u, v, w) = tt;
if(d[u] < d[v]) swap(u, v); // make sure only one possible == lca
int lca = get_lca(u, v);
if(d[u] + d[v] - 2*d[lca] & 1) continue;
int i = tmp.size();
ls[lca].push_back(i);
if(u != lca) upar[i] = get_par(u, d[u] - d[lca] - 1);
if(v != lca) vpar[i] = get_par(v, d[v] - d[lca] - 1);
tmp.emplace_back(u, v, w);
}
unpaved = tmp;
dfs(1, 0);
cout << sum - dp[1][1];
}
Compilation message
training.cpp: In function 'void init_lca(int, int)':
training.cpp:16:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
for(int j = 0; 1 << j+1 <= d[v]; j++) anc[v].push_back(anc[anc[v][j]][j]);
~^~
training.cpp: In function 'int get_lca(int, int)':
training.cpp:22:43: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for(int j = 0; d[u] > d[v]; j++) if(d[u] - d[v] >> j & 1) u = anc[u][j];
~~~~~^~~~~~
training.cpp:24:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 10; j >= 0; j--) if(j < anc[u].size() && anc[u][j] != anc[v][j])
~~^~~~~~~~~~~~~~~
training.cpp: In function 'void dfs(int, int)':
training.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ord.size(); i++) {
~~^~~~~~~~~~~~
training.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ord.size(); i++) {
~~^~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:98:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
if(d[u] + d[v] - 2*d[lca] & 1) continue;
~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
828 KB |
Output is correct |
| 2 |
Correct |
4 ms |
864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
5012 KB |
Output is correct |
| 2 |
Correct |
20 ms |
5224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
5224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
5436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
