#include<bits/stdc++.h>
using namespace std;
long long P[1005][19],timer,in[5005],out[5005];
long long n,m,ran[5005],lvl[5005],t[1405][5005];
vector<long long>v[5005];
vector<pair<long long,pair<long long,long long> > >g[5005];
long long dp[1005][1400];
bool don[1005][1400],tu[1405][5005];
void go(long long x,long long 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];
}
long long solve(long long x,long long mask){
if(don[x][mask])return dp[x][mask];
don[x][mask] = 1;
long long 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++){
long long a = g[x][i].first , b = g[x][i].second.first , c = g[x][i].second.second;
long long pa = -1, push_back = -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]){
push_back = j;
}
}
if(pa != -1 && (mask & (1 << pa)))continue;
if(push_back != -1 && (mask & (1 << push_back)))continue;
long long k = a,ne = mask;
if(pa != -1)ne ^= (1 << pa);
if(push_back != -1)ne ^= (1 << push_back);
long long 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);
long long 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].second.second;
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;
long long sum = 0;
vector<pair<long long,pair<long long,long long> > >ed;
for(int i=1; i<=m; i++){
long long x,y,z;
cin >> x >> y >> z;
sum += z;
if(z == 0){
v[x].push_back(y);
v[y].push_back(x);
}
else {
ed.push_back(make_pair(x , make_pair(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]].push_back(i);
}
for(int i=0; i<ed.size(); i++){
long long x = ed[i].first , y = ed[i].second.first , z = ed[i].second.second;
long long p = lca(x , y);
if((lvl[x] + lvl[y] - 2 * lvl[p]) % 2 == 1)continue;
g[p].push_back(make_pair(x , make_pair(y , z)));
}
cout << sum - solve(1 , 0) << '\n';
}
Compilation message
training.cpp: In function 'void go(long long int, long long int)':
training.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i=0; i<v[x].size(); i++){
| ~^~~~~~~~~~~~
training.cpp: In function 'long long int solve(long long int, long long int)':
training.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0; i<v[x].size(); i++){
| ~^~~~~~~~~~~~
training.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0; i<g[x].size(); i++){
| ~^~~~~~~~~~~~
training.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int j=0; j<v[x].size(); j++){
| ~^~~~~~~~~~~~
training.cpp:48:66: warning: unused variable 'c' [-Wunused-variable]
48 | long long a = g[x][i].first , b = g[x][i].second.first , c = g[x][i].second.second;
| ^
training.cpp: In function 'int main()':
training.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=0; i<ed.size(); i++){
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
716 KB |
Output is correct |
| 2 |
Correct |
1 ms |
716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
9528 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10956 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
716 KB |
Output is correct |
| 2 |
Correct |
2 ms |
688 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
820 KB |
Output is correct |
| 2 |
Correct |
1 ms |
716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1356 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2744 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2508 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
4428 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3916 KB |
Output is correct |
| 3 |
Correct |
37 ms |
3788 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
8012 KB |
Output is correct |
| 2 |
Correct |
38 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7372 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
3788 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4800 KB |
Output is correct |
| 3 |
Correct |
65 ms |
6596 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4172 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
7000 KB |
Output is correct |
| 2 |
Correct |
40 ms |
8908 KB |
Output is correct |
| 3 |
Correct |
12 ms |
7500 KB |
Output is correct |
| 4 |
Correct |
33 ms |
7888 KB |
Output is correct |
