#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;
const int maxn = 1e3 + 10;
int n, m, h[maxn], jump[maxn][11], get_idx[maxn], dp[10][1<<10][maxn];
map<pii, int> path;
vector<int> adj[maxn], x[maxn];
vector<pair<pii, int>> edge;
vector<pair<pii, pii>> connections[maxn]; // {{cost, child}, {node, node_child}}
void dfs(int v, int p, int height){
jump[v][0] = p; h[v] = height;
int idx = 0;
for (auto u : adj[v]){
if (u == p) continue;
get_idx[u] = idx++; x[v].PB(u);
dfs(u, v, height + 1);
}
}
void lca_add(int a, int b, int c){
// h[a] >= h[b]
int start_a = a, start_b = b;
for (int p = 10; p >= 0; p--){
if (h[jump[a][p]] > h[b]) a = jump[a][p];
}
if (jump[a][0] == b){
connections[a].PB({{c, a}, {b, start_a}});
return;
}
if (h[jump[a][0]] == h[b]) a = jump[a][0];
for (int p = 10; p >= 0; p--){
if (jump[a][p] != jump[b][p]) a = jump[a][p], b = jump[b][p];
}
connections[a].PB({{c, start_a}, {b, start_b}});
connections[b].PB({{c, start_b}, {a, start_a}});
}
int solve(int idx, int mask, int p);
int path_cost(int p, int v){
if (path.count({p, v})) return path[{p, v}];
int re = 0, last = -1;
while (v != p){
int mask = 0;
if (last != -1) mask |= (1<<get_idx[last]);
re += solve(0, mask, v);
last = v;
v = jump[v][0];
}
path[{p, v}] = re;
return re;
}
int solve(int idx, int mask, int p){
if (idx >= x[p].size()) return 0;
if (dp[idx][mask][p] != -1) return dp[idx][mask][p];
int v = x[p][idx];
int re = solve(idx + 1, mask, p); // takent
if (mask&(1<<idx)) return re;
re += solve(0, 0, v);
int take_mask = mask|(1<<idx);
for (auto c : connections[v]){
int cost = c.F.F, child = c.F.S, u = c.S.F, u_child = c.S.S;
if (get_idx[u] < idx && u != p) continue;
if (mask&(1<<get_idx[u]) && u != p) continue;
int take = 0;
if (u == p){ // connects to parent
take = solve(idx + 1, take_mask, p) + cost;
take += path_cost(p, u_child);
}
else{
take = solve(idx + 1, take_mask|(1<<get_idx[u]), p) + cost;
take += path_cost(p, child);
take += path_cost(p, u_child);
}
re = max(re, take);
}
dp[idx][mask][p] = re;
return dp[idx][mask][p];
}
signed main(){
NYOOM;
fill(&dp[0][0][0], &dp[0][0][0] + 10 * (1<<10) * maxn, -1);
cin >> n >> m;
int sum = 0;
FOR(i, m){
int a, b, c; cin >> a >> b >> c;
sum += c;
if (c == 0){
adj[a].PB(b); adj[b].PB(a);
}
else{
edge.PB({{a, b}, c});
}
}
dfs(1, 1, 0);
for (int p = 1; p <= 10; p++){
for (int i = 1; i <= n; i++){
jump[i][p] = jump[jump[i][p - 1]][p - 1];
}
}
for (auto x : edge){
int a = x.F.F, b = x.F.S, c = x.S;
if (abs(h[a] - h[b]) % 2){
// if connects two nodes odd dist apart = can't include
continue;
}
if (h[a] < h[b]) swap(a, b);
lca_add(a, b, c);
}
cout << sum - solve(0, 0, 1);
}
Compilation message
training.cpp: In function 'int solve(int, int, int)':
training.cpp:69:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if (idx >= x[p].size()) return 0;
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
40788 KB |
Output is correct |
| 2 |
Correct |
16 ms |
40828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
40832 KB |
Output is correct |
| 2 |
Correct |
17 ms |
40844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
41156 KB |
Output is correct |
| 2 |
Correct |
27 ms |
41172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
40772 KB |
Output is correct |
| 2 |
Correct |
16 ms |
40880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
40916 KB |
Output is correct |
| 2 |
Correct |
16 ms |
40832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
40784 KB |
Output is correct |
| 2 |
Correct |
17 ms |
40876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
40916 KB |
Output is correct |
| 2 |
Correct |
17 ms |
40924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
40916 KB |
Output is correct |
| 2 |
Correct |
18 ms |
41020 KB |
Output is correct |
| 3 |
Correct |
61 ms |
41064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
41172 KB |
Output is correct |
| 2 |
Correct |
32 ms |
41144 KB |
Output is correct |
| 3 |
Correct |
24 ms |
41340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
41044 KB |
Output is correct |
| 2 |
Correct |
19 ms |
41028 KB |
Output is correct |
| 3 |
Correct |
125 ms |
41420 KB |
Output is correct |
| 4 |
Correct |
19 ms |
41068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
41172 KB |
Output is correct |
| 2 |
Correct |
121 ms |
41236 KB |
Output is correct |
| 3 |
Correct |
22 ms |
41152 KB |
Output is correct |
| 4 |
Correct |
32 ms |
41224 KB |
Output is correct |
