#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int p[N][20], dp[N], tmin[N], tmout[N], timer, UP[N];
vector<int> t[N];
vector<int> x[N];
vector<pair<pii,int >> E[N];
bool check(int u, int v) {
return (tmin[u] <= tmin[v] && tmout[u] >= tmout[v]);
}
int lca(int u, int v) {
if(check(u, v)) return u;
if(check(v, u)) return v;
for(int i = 16; i >= 0; i--) {
if(p[u][i] && !check(p[u][i], v)) v = p[u][i];
}
return p[u][0];
}
void dfs1(int u, int P) {
tmin[u] = ++timer;
p[u][0] = P;
for(int i = 1; i <= 16; i++) p[u][i] = p[p[u][i - 1]][i - 1];
for(int i = 0; i < t[u].size(); i++) {
if(t[u][i] == P) continue;
UP[t[u][i]] = i;
p[t[u][i]][0] = u;
dfs1(t[u][i], u);
}
tmout[u] = timer;
}
int up(int a, int u) {
int ans = (a == u ? 0 : dp[a]);
vector<int> v;
while(a != u) {
v.push_back(a);
a = p[a][0];
}
return ans;
}
int get(int l, int a, int b) {
int x = 0;
for(int i = 0; i < t[l].size(); i++) {
if(t[l][i] != p[l][0] && check(t[l][i], a)) x += 1 << i;
if(t[l][i] != p[l][0] && check(t[l][i], b)) x += 1 << i;
}
return x;
}
void dfs(int u, int p) {
for(int i = 0; i < t[u].size(); i++) {
if(t[u][i] == p) continue;
dfs(t[u][i], u);
dp[u] = max(dp[u], dp[t[u][i]]);
}
x[u].resize(1 << (int)t[u].size());
for(int j = 0; j < E[u].size(); j++) {
int a = E[u][j].f.f, b = E[u][j].f.s, c = E[u][j].s;
// u dan zevit
if(b == u) swap(a, b);
dp[u] = max(dp[u], dp[b] + c);
return;
c += up(a, u) + up(b, u);
int bb = get(u, a, b);
assert(up(a, u) >= 0); assert(up(b, u) >= 0);
for(int mask = (1 << (int)t[u].size()) - 1; mask >= 0; --mask) {
if(!(mask & bb))
x[u][mask + bb] = max(x[u][mask + bb], x[u][mask] + c);
}
}
for(int mask = 0; mask < (1 << (int)t[u].size()); ++mask) {
for(int i = 0; i < t[u].size(); ++i) if(mask & (1 << i)) x[u][mask] = max(x[u][mask], x[u][mask ^ (1 << i)]);
}
for(int mask = 0; mask < (1 << (int)t[u].size()); ++mask) {
int cur = x[u][mask];
for(int i = 0; i < t[u].size(); i++) {
if(t[u][i] == p) continue;
if(!(mask& (1 << i))) x[u][mask ^ (1 << i)] = max(x[u][mask ^ (1 << i)] , x[u][mask] + dp[t[u][i]]);
}
dp[u] = max(dp[u], x[u][mask]);
}
}
main(){
int n, m, cost = 0;
cin >> n >> m;
vector<pair<pii,int> > e;
for(int i = 1; i <= m; i++) {
int u, v, c;
cin >> u >> v >> c;
if(!c) t[u].push_back(v), t[v].push_back(u);
else e.push_back({{u, v}, c});
cost += c;
}
dfs1(1, 0);
for(int i = 0; i < e.size(); ++i) {
int u = e[i].f.f, v = e[i].f.s, c = e[i].s;
E[lca(u, v)].push_back({{u, v}, c});
}
dfs(1, 1);
cout << cost - dp[1] << endl;
}
Compilation message
training.cpp: In function 'void dfs1(long long int, long long int)':
training.cpp:28:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0; i < t[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp: In function 'long long int get(long long int, long long int, long long int)':
training.cpp:49:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i < t[l].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp: In function 'void dfs(long long int, long long int)':
training.cpp:56:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i = 0; i < t[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp:62:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int j = 0; j < E[u].size(); j++) {
| ~~^~~~~~~~~~~~~
training.cpp:80:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 0; i < t[u].size(); ++i) if(mask & (1 << i)) x[u][mask] = max(x[u][mask], x[u][mask ^ (1 << i)]);
| ~~^~~~~~~~~~~~~
training.cpp:84:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0; i < t[u].size(); i++) {
| ~~^~~~~~~~~~~~~
training.cpp:83:13: warning: unused variable 'cur' [-Wunused-variable]
83 | int cur = x[u][mask];
| ^~~
training.cpp: At global scope:
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:107:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < e.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
15060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
15044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
