#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1000;
const int maxd=10;
struct bare{
int a, b, c;
};
vector<int> adjlis[maxn];
int root;
int depth[maxn];
int parent[maxn];
int fap[maxn], sap[maxn];
int et;
void dfs1(int x=root){
fap[x]=et++;
for(int y : adjlis[x]){
adjlis[y].erase(find(adjlis[y].begin(), adjlis[y].end(), x));
depth[y]=depth[x]+1;
parent[y]=x;
dfs1(y);
}
sap[x]=et;
}
int lca(int x, int y){
if(depth[x]>depth[y])
swap(x, y);
while(depth[x]<depth[y])
y=parent[y];
while(x!=y)
x=parent[x], y=parent[y];
return x;
}
vector<bare> paths[maxn];
const int uncalculated=-1000000000;
int memo[maxn][maxn];
int memo2[maxn][maxd];
int dfs2(int x=root, int bad=root){
int& ret=memo[x][bad];
if(ret!=uncalculated)
return ret;
if(x==bad){
int sz=1<<adjlis[x].size();
int dp[sz];
fill(dp, dp+sz, 0);
for(const auto& i : paths[x]){
int rec=i.c;
int index=0;
if(i.a!=x){
for(int j=0; j<adjlis[x].size(); j++){
if(fap[adjlis[x][j]]<=fap[i.a] and sap[i.a]<=sap[adjlis[x][j]]){
index|=1<<j;
rec+=dfs2(adjlis[x][j], i.a)-dfs2(adjlis[x][j], adjlis[x][j]);
break;
}
}
}
if(i.b!=x){
for(int j=0; j<adjlis[x].size(); j++){
if(fap[adjlis[x][j]]<=fap[i.b] and sap[i.b]<=sap[adjlis[x][j]]){
index|=1<<j;
rec+=dfs2(adjlis[x][j], i.b)-dfs2(adjlis[x][j], adjlis[x][j]);
break;
}
}
}
dp[index]=max(dp[index], rec);
}
for(int k=0; k<sz; k++)for(int i=k; i+i>k; i=i-1&k)
dp[k]=max(dp[k], dp[i]+dp[k^i]);
ret=dp[sz-1];
for(int y : adjlis[x])
ret+=dfs2(y, y);
return ret;
}else{
int banned;
for(int i=0; i<adjlis[x].size(); i++){
if(fap[adjlis[x][i]]<=fap[bad] and sap[bad]<=sap[adjlis[x][i]]){
banned=i;
break;
}
}
int sz=1<<adjlis[x].size();
int dp[sz];
fill(dp, dp+sz, 0);
for(const auto& i : paths[x]){
int rec=i.c;
int index=0;
if(i.a!=x){
for(int j=0; j<adjlis[x].size(); j++){
if(fap[adjlis[x][j]]<=fap[i.a] and sap[i.a]<=sap[adjlis[x][j]]){
index|=1<<j;
rec+=dfs2(adjlis[x][j], i.a)-dfs2(adjlis[x][j], adjlis[x][j]);
break;
}
}
}
if(i.b!=x){
for(int j=0; j<adjlis[x].size(); j++){
if(fap[adjlis[x][j]]<=fap[i.b] and sap[i.b]<=sap[adjlis[x][j]]){
index|=1<<j;
rec+=dfs2(adjlis[x][j], i.b)-dfs2(adjlis[x][j], adjlis[x][j]);
break;
}
}
}
if(index>>banned&1)
continue;
dp[index]=max(dp[index], rec);
}
for(int k=0; k<sz; k++)for(int i=k; i+i>k; i=i-1&k)
dp[k]=max(dp[k], dp[i]+dp[k^i]);
ret=dp[sz-1];
for(int i=0; i<adjlis[x].size(); i++){
if(i==banned){
ret+=dfs2(adjlis[x][i], bad);
}else{
ret+=dfs2(adjlis[x][i], adjlis[x][i]);
}
}
return ret;
}
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
vector<bare> bares;
for(int i=m; i--;){
int a, b, c;
scanf("%d%d%d", &a, &b, &c), a--, b--;
if(c){
bares.push_back(bare{a, b, c});
}else{
adjlis[a].push_back(b);
adjlis[b].push_back(a);
}
}
for(int i=n; i--;){
if(adjlis[i].size()==1)
root=i;
}
depth[root]=0;
et=0;
dfs1();
int ans=0;
for(auto& i : bares){
ans+=i.c;
if(~(depth[i.a]+depth[i.b])&1)
paths[lca(i.a, i.b)].push_back(i);
}
for(int i=0; i<n; i++){
fill(memo[i], memo[i]+n, uncalculated);
fill(memo2[i], memo2[i]+maxd, uncalculated);
}
printf("%d\n", ans-dfs2());
}
Compilation message
training.cpp: In function 'int dfs2(int, int)':
training.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int j=0; j<adjlis[x].size(); j++){
| ~^~~~~~~~~~~~~~~~~
training.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int j=0; j<adjlis[x].size(); j++){
| ~^~~~~~~~~~~~~~~~~
training.cpp:71:49: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
71 | for(int k=0; k<sz; k++)for(int i=k; i+i>k; i=i-1&k)
| ~^~
training.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0; i<adjlis[x].size(); i++){
| ~^~~~~~~~~~~~~~~~~
training.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int j=0; j<adjlis[x].size(); j++){
| ~^~~~~~~~~~~~~~~~~
training.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int j=0; j<adjlis[x].size(); j++){
| ~^~~~~~~~~~~~~~~~~
training.cpp:113:49: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
113 | for(int k=0; k<sz; k++)for(int i=k; i+i>k; i=i-1&k)
| ~^~
training.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i=0; i<adjlis[x].size(); i++){
| ~^~~~~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
training.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d%d%d", &a, &b, &c), a--, b--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
training.cpp: In function 'int dfs2(int, int)':
training.cpp:78:7: warning: 'banned' may be used uninitialized in this function [-Wmaybe-uninitialized]
78 | int banned;
| ^~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
26 ms |
4576 KB |
Output is correct |
| 2 |
Correct |
29 ms |
4556 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
716 KB |
Output is correct |
| 2 |
Correct |
1 ms |
716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1484 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
20 ms |
2428 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
55 ms |
4448 KB |
Output is correct |
| 2 |
Correct |
56 ms |
4428 KB |
Output is correct |
| 3 |
Correct |
43 ms |
4496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
31 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
22 ms |
2380 KB |
Output is correct |
| 3 |
Correct |
71 ms |
4556 KB |
Output is correct |
| 4 |
Correct |
19 ms |
2380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
86 ms |
4540 KB |
Output is correct |
| 2 |
Correct |
22 ms |
4604 KB |
Output is correct |
| 3 |
Correct |
178 ms |
4568 KB |
Output is correct |
| 4 |
Correct |
72 ms |
4408 KB |
Output is correct |
