#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll P[1005][19],timer,in[5005],out[5005];
ll n,m,ran[5005],lvl[5005],t[1405][5005];
vector<ll>v[5005];
vector<pair<ll,pair<ll,ll> > >g[5005];
ll dp[1005][1400];
bool don[1005][1400],tu[1405][5005];
void go(ll x,ll par){
P[x][0]=par;
for (int i=1;i<=13;i++)
P[x][i]=P[P[x][i-1]][i-1];
timer++;
in[x]=timer;
for(int i=0; i<v[x].size(); i++){
if(v[x][i] != par){
lvl[v[x][i]] = lvl[x] + 1;
go(v[x][i] , x);
}
}
timer++;
out[x] = timer;
}
int lca(int a,int b) {
if(lvl[a] > lvl[b])swap(a,b);
if(in[a] <= in[b] && out[b] <= out[a])return a;
for(int i=13;i>=0;i--)
if(P[a][i])
if(!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]]))
a=P[a][i];
return P[a][0];
}
ll solve(ll x,ll mask){
if(don[x][mask])return dp[x][mask];
don[x][mask] = 1;
ll fi = 0,r = 0;
for(int i=0; i<v[x].size(); i++){
ran[v[x][i]] = r;
r++;
if(mask & (1 << i))continue;
solve(v[x][i] , 0);
fi += dp[v[x][i]][0];
}
dp[x][mask] = fi;
for(int i=0; i<g[x].size(); i++){
ll a = g[x][i].f , b = g[x][i].s.f , c = g[x][i].s.s;
ll pa = -1, pb = -1;
for(int j=0; j<v[x].size(); j++){
if(in[v[x][j]] <= in[a] && out[v[x][j]] >= out[a]){
pa = j;
}
if(in[v[x][j]] <= in[b] && out[v[x][j]] >= out[b]){
pb = j;
}
}
if(pa != -1 && (mask & (1 << pa)))continue;
if(pb != -1 && (mask & (1 << pb)))continue;
ll k = a,ne = mask;
if(pa != -1)ne ^= (1 << pa);
if(pb != -1)ne ^= (1 << pb);
ll ad = solve(x , ne),cur = 0;
if(tu[x][i]){
dp[x][mask] = max(dp[x][mask] , ad + t[x][i]);
continue;
}
tu[x][i] = 1;
if(k != x)cur += solve(k , 0);
ll pre = k;
while(k != x){
k = P[k][0];
if(k == x)break;
cur += solve(k , (1 << ran[pre]));
pre = k;
}
k = b;
if(k != x)cur += solve(k , 0);
pre = k;
while(k != x){
k = P[k][0];
if(k == x)break;
cur += solve(k , (1 << ran[pre]));
pre = k;
}
cur += g[x][i].s.s;
t[x][i] = cur;
dp[x][mask] = max(dp[x][mask] , ad + cur);
}
return dp[x][mask];
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
ll sum = 0;
vector<pair<ll,pair<ll,ll> > >ed;
for(int i=1; i<=m; i++){
ll x,y,z;
cin >> x >> y >> z;
sum += z;
if(z == 0){
v[x].pb(y);
v[y].pb(x);
}
else {
ed.pb(mp(x , mp(y , z)));
}
}
go(1 , 0);
for(int i=1; i<=n; i++)
v[i].clear();
for(int i=2; i<=n; i++){
v[P[i][0]].pb(i);
}
for(int i=0; i<ed.size(); i++){
ll x = ed[i].f , y = ed[i].s.f , z = ed[i].s.s;
ll p = lca(x , y);
if((lvl[x] + lvl[y] - 2 * lvl[p]) % 2 == 1)continue;
g[p].pb(mp(x , mp(y , z)));
}
cout << sum - solve(1 , 0) << '\n';
return 0;
}
Compilation message
training.cpp: In function 'void go(int, int)':
training.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0; i<v[x].size(); i++){
| ~^~~~~~~~~~~~
training.cpp: In function 'int solve(int, int)':
training.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0; i<v[x].size(); i++){
| ~^~~~~~~~~~~~
training.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0; i<g[x].size(); i++){
| ~^~~~~~~~~~~~
training.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int j=0; j<v[x].size(); j++){
| ~^~~~~~~~~~~~
training.cpp:51:46: warning: unused variable 'c' [-Wunused-variable]
51 | ll a = g[x][i].f , b = g[x][i].s.f , c = g[x][i].s.s;
| ^
training.cpp: In function 'int main()':
training.cpp:121:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i=0; i<ed.size(); i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
9452 KB |
Output is correct |
| 2 |
Correct |
12 ms |
10732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
876 KB |
Output is correct |
| 2 |
Correct |
1 ms |
876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4460 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3820 KB |
Output is correct |
| 3 |
Correct |
45 ms |
3692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7788 KB |
Output is correct |
| 2 |
Correct |
39 ms |
6508 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3692 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4716 KB |
Output is correct |
| 3 |
Correct |
58 ms |
6508 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
6764 KB |
Output is correct |
| 2 |
Correct |
41 ms |
8684 KB |
Output is correct |
| 3 |
Correct |
12 ms |
7148 KB |
Output is correct |
| 4 |
Correct |
33 ms |
7532 KB |
Output is correct |
