# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5005;
int t,n,m,a[N],in[N],out[N],tin, dp[N][1025],id[N][N];
int par[N],lv[N];
vector <int> v[N];
void dfs(int a, int p) {
in[a] = ++tin;
par[a] = p;
lv[a] = lv[p] + 1;
for (int to : v[a]) {
if (to == p) continue;
dfs(to, a);
}
out[a] = tin;
}
int upper(int a, int b) {
return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
int cur = a;
while (!upper(cur, b)) {
cur = par[cur];
}
return cur;
}
int get(int a, int p) {
int cur = a, lst = -1, ans = 0;
while (cur != p) {
if (lst == -1) ans += dp[cur][0];
else ans += dp[cur][(1<<id[cur][lst])];
lst = cur;
cur = par[cur];
}
return ans;
}
vector <array <int, 3> > g[N];
int kth(int x, int k) {
while (k--) {
x = par[x];
}
return x;
}
void dfs1(int a, int p) {
int cnt = 0;
for (int to : v[a]) {
if (to == p) continue;
id[a][to] = cnt;
cnt++;
dfs1(to, a);
}
vector <array <int, 4> > pot;
for (array <int, 3> edge : g[a]) {
int x = edge[0], y = edge[1], z = edge[2];
int msk = 0;
if (a != x) {
int getx = kth(x, lv[x] - lv[a] - 1);
msk |= (1<<id[a][getx]);
}
if (a != y) {
int gety = kth(y, lv[y] - lv[a] - 1);
msk |= (1<<id[a][gety]);
}
pot.pb({x, y, z, msk});
}
for (int to : v[a]) {
if(to == p) continue;
int sz = (int)v[to].size() - 1;
int mx = 0;
for (int msk = 0; msk < (1<<sz); msk++) mx = max(mx, dp[to][msk]);
dp[a][0] += mx;
}
for (array <int, 4> edge : pot) {
int x = edge[0], y = edge[1], z = edge[2], cur_mask = edge[3];
//cout<<a<<" --- > "<<x<<" "<<y<<" "<<z<<" "<<cur_mask<<"\n";
for (int msk = (1<<cnt) - 1; msk >= 0; msk--) {
if ((msk & cur_mask)) continue;
int cur_pas = dp[a][msk | cur_mask]; // add(x -- y) wibo
cur_pas += get(x, a) + get(y, a) + z;
dp[a][msk] = max(dp[a][msk], cur_pas);
}
//cout<<a<<" "<<dp[a][0]<<" "<<dp[a][1]<<"\n";
}
}
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
vector < array <int, 3 > > vec, vn;
int sum = 0;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin>>a>>b>>c;
sum += c;
if (c == 0) {
v[a].pb(b);
v[b].pb(a);
} else {
vec.pb({a, b, c});
}
}
dfs(1, 0);
for (array <int, 3> x : vec) {
int a = x[0], b = x[1], c = x[2];
int dist = lv[a] + lv[b] - 2 * lv[lca(a, b)];
if (dist % 2 == 1) { // delete
} else vn.pb(x);
}
vec = vn;
for (array <int, 3> x : vec) {
int a = x[0], b = x[1], c = x[2];
//cout<<a<<" "<<b<<" "<<c<<"\n";
g[lca(a, b)].pb({a,b,c});
}
dfs1(1, 0);
cout<<sum - dp[1][0]<<"\n";
}
Compilation message
training.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
93 | main() {
| ^~~~
training.cpp: In function 'int main()':
training.cpp:111:27: warning: unused variable 'c' [-Wunused-variable]
111 | int a = x[0], b = x[1], c = x[2];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
8916 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
5236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
