#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int DIM = 1e3 + 5;
struct drum {
int x, y, c;
};
int n, m;
int tt[DIM], h[DIM], dp[DIM];
bool viz[DIM];
int mark[DIM];
vector <int> arb[DIM];
vector <pair <int, int>> v[DIM];
vector <drum> path[DIM];
vector <int> l;
int lca(int x, int y) {
while (x != y) {
if (h[x] > h[y]) x = tt[x];
else y = tt[y];
}
return x;
}
bool mark_road(int nod, int now) {
if (now == nod) return true;
l.push_back(now);
++mark[now];
if (mark[now] >= 2) return false;
return mark_road(nod, tt[now]);
}
void unmark_road(int sz) {
if ((int)l.size() == sz) return ;
--mark[l.back()];
l.pop_back();
unmark_road(sz);
}
void back(int ind, int nod, int end, int sum = 0) {
if (ind == end) {
for (auto cur : l) {
for (auto fiu : arb[cur]) {
if (fiu != tt[cur] && !mark[fiu])
sum = sum + dp[fiu];
}
}
dp[nod] = max(dp[nod], sum);
return ;
}
int sz = l.size();
back(ind + 1, nod, end, sum);
bool ok = mark_road(nod, v[nod][ind].x);
if (ok)
back(ind + 1, nod, end, sum + v[nod][ind].y + dp[v[nod][ind].x]);
unmark_road(sz);
}
void dfs(int nod = 1, int papa = 0) {
for (auto it : arb[nod]) {
if (it == papa) continue ;
h[it] = h[nod] + 1;
dfs(it, nod);
tt[it] = nod;
}
}
void solve(int nod = 1, int papa = 0) {
for (auto it : arb[nod]) {
if (it == papa) continue ;
solve(it, nod);
dp[nod] += dp[it];
}
back(0, nod, v[nod].size(), 0);
for (auto it : path[nod]) {
mark_road(nod, it.x); mark_road(nod, it.y);
back(0, nod, v[nod].size(), it.c + dp[it.x] + dp[it.y]);
unmark_road(0);
}
}
int main() {
scanf("%d%d", &n, &m);
int x, y, c;
int sum = 0;
vector <tuple<int, int, int>> edges;
for (int i = 1; i <= m ; ++i) {
scanf("%d%d%d", &x, &y, &c);
if (c == 0) {
arb[x].push_back(y);
arb[y].push_back(x);
} else {
edges.push_back({x, y, c});
}
}
dfs();
for (auto it : edges) {
x = get<0>(it);
y = get<1>(it);
c = get<2>(it);
sum += c;
int z = lca(x, y);
if ((h[x] - h[z] + h[y] - h[z] + 1) % 2 == 0) continue ;
if (z == x) v[z].push_back({y, c});
else if (z == y) v[z].push_back({x, c});
else path[z].push_back({x, y, c});
}
solve();
printf("%d", sum - dp[1]);
return 0;
}
Compilation message
training.cpp: In function 'int main()':
training.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
95 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
training.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
103 | scanf("%d%d%d", &x, &y, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
