#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
int up[1010][11], depth[1010], num[1010], sz[1010], timeDfs;
int dp[1010][1 << 10], dpFull[1010], calc[1010];
vector<int> adj[1010];
vector<tt> paths[1010];
int preDfs (int u, int p, int d) {
up[u][0] = p, depth[u] = d, num[u] = ++timeDfs, sz[u] = 1;
for (int i = 1; i < 11; i++)
up[u][i] = up[up[u][i - 1]][i - 1];
for (int v : adj[u])
if (v != p) sz[u] += preDfs(v, u, d + 1);
return sz[u];
}
int goUp (int a, int k) {
for (int i = 0; i < 11; i++)
if (k & (1 << i)) a = up[a][i];
return a;
}
int lca (int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
a = goUp(a, depth[a] - depth[b]);
if (a == b) return a;
for (int i = 10; i >= 0; i--)
if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
return up[a][0];
}
bool getCur (int mask, int pos) {
return mask & (1 << pos);
}
int cur;
void dfs (int u, int p) {
calc[u] = cur + dpFull[u];
int fullMask = (1 << adj[u].size()) - 1;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i]; if (v == p) continue;
cur += dp[u][fullMask ^ (1 << i)];
dfs(v, u);
cur -= dp[u][fullMask ^ (1 << i)];
}
}
bool inTree (int root, int u) {
return num[root] <= num[u] && num[u] < num[root] + sz[root];
}
void solve (int u, int p) {
for (int v : adj[u]) {
if (v == p) continue;
solve(v, u), dfs(v, u);
}
for (int allow = 0; allow < (1 << adj[u].size()); allow++) {
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (!getCur(allow, i) || v == p) continue;
dp[u][allow] += dpFull[v];
}
for (tt path : paths[u]) {
int a, b, cost, mask = 0; tie(a, b, cost) = path;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i]; if (v == p) continue;
if (inTree(v, a)) mask |= (1 << i);
if (inTree(v, b)) mask |= (1 << i);
}
if ((allow & mask) == mask)
dp[u][allow] = max(dp[u][allow], dp[u][allow ^ mask] + calc[a] + calc[b] + cost);
}
}
dpFull[u] = dp[u][(1 << adj[u].size()) - 1];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, sum = 0; cin >> n >> m;
vector<tt> unpaved;
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
if (c) {
unpaved.emplace_back(a, b, c);
sum += c;
}
else {
adj[a].push_back(b);
adj[b].push_back(a);
}
}
preDfs(1, 1, 1);
for (tt it : unpaved) {
int a, b, c; tie(a, b, c) = it;
if (depth[a] % 2 == depth[b] % 2)
paths[lca(a, b)].push_back(it);
}
solve(1, 1);
cout << sum - dpFull[1];
return 0;
}
Compilation message
training.cpp: In function 'void dfs(int, int)':
training.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
training.cpp: In function 'void solve(int, int)':
training.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
training.cpp:79:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
10 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
3 ms |
860 KB |
Output is correct |
| 3 |
Correct |
35 ms |
1628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2140 KB |
Output is correct |
| 2 |
Correct |
45 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
856 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
58 ms |
4680 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
2316 KB |
Output is correct |
| 2 |
Correct |
39 ms |
4692 KB |
Output is correct |
| 3 |
Correct |
21 ms |
1760 KB |
Output is correct |
| 4 |
Correct |
47 ms |
1616 KB |
Output is correct |
