#include <bits/stdc++.h>
using namespace std;
vector <int> V[1010], T[1010];
int P[1010], D[1010];
int M[1010][1010];
int A[5050], B[5050], C[5050];
int X[1010][1100];
int n, m, k, sum, ans;
void dfs(int p, int r)
{
for(auto t: T[p]){
if(t != r){
P[t] = p;
D[t] = D[p] + 1;
dfs(t, p);
}
}
}
int lca(int a, int b)
{
if(D[a] < D[b]) swap(a, b);
for(;D[a] != D[b];) a = P[a];
for(;a != b;) a = P[a], b = P[b];
return a;
}
void dp(int p, int r)
{
int a, b, x, y, s, i;
int cnt = 0;
for(auto t: T[p]){
if(t != r){
dp(t, p);
cnt += X[t][1023];
}
}
for(i=0;i<1024;i++) X[p][i] = cnt;
for(auto t: V[p]){
a = A[t], b = B[t], s = C[t];
x = y = 0;
for(;a!=p;){
if(x) s += X[a][1023 - (1 << M[a][x])] - X[x][1023];
else s += X[a][1023];
x = a, a = P[a];
}
for(;b!=p;){
if(y) s += X[b][1023 - (1 << M[b][y])] - X[y][1023];
else s += X[b][1023];
y = b, b = P[b];
}
b = 0;
if(x) s -= X[x][1023], b |= 1 << M[p][x];
if(y) s -= X[y][1023], b |= 1 << M[p][y];
// printf("* %d %d\n", b, s);
for(i=0;i<1024;i++) if(!(i & b)){
X[p][i+b] = max(X[p][i+b], X[p][i] + s);
}
}
// printf("%d %d\n", p, X[p][1023]);
}
int main()
{
int i, j, a, b, c;
scanf("%d%d", &n, &m);
for(i=0;i<m;i++){
scanf("%d%d%d", &a, &b, &c);
if(c == 0) T[a].push_back(b), T[b].push_back(a);
else A[k] = a, B[k] = b, C[k++] = c;
sum += c;
}
for(i=1;i<=n;i++){
for(j=0;j<T[i].size();j++){
M[i][T[i][j]] = j;
}
}
dfs(1, 0);
for(i=0;i<k;i++){
if(~(D[A[i]] + D[B[i]]) & 1){
V[lca(A[i], B[i])].push_back(i);
}
}
dp(1, 0);
for(i=0;i<1024;i++){
ans = max(ans, X[1][i]);
}
printf("%d\n", sum - ans);
return 0;
}
Compilation message
training.cpp: In function 'int main()':
training.cpp:91:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<T[i].size();j++){
~^~~~~~~~~~~~
training.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
training.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
912 KB |
Output is correct |
2 |
Correct |
3 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
8984 KB |
Output is correct |
2 |
Correct |
15 ms |
8984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8984 KB |
Output is correct |
2 |
Correct |
2 ms |
8984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
8984 KB |
Output is correct |
2 |
Correct |
2 ms |
8984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
8984 KB |
Output is correct |
2 |
Correct |
3 ms |
8984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
8984 KB |
Output is correct |
2 |
Correct |
5 ms |
8984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8984 KB |
Output is correct |
2 |
Correct |
8 ms |
8984 KB |
Output is correct |
3 |
Correct |
8 ms |
8984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
8984 KB |
Output is correct |
2 |
Correct |
14 ms |
8984 KB |
Output is correct |
3 |
Correct |
14 ms |
8984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8984 KB |
Output is correct |
2 |
Correct |
9 ms |
8984 KB |
Output is correct |
3 |
Correct |
22 ms |
9012 KB |
Output is correct |
4 |
Correct |
9 ms |
9012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
9012 KB |
Output is correct |
2 |
Correct |
22 ms |
9012 KB |
Output is correct |
3 |
Correct |
17 ms |
9012 KB |
Output is correct |
4 |
Correct |
14 ms |
9012 KB |
Output is correct |