#include <cstdio>
#include <vector>
#include <array>
#include <algorithm>
std::vector<std::array<int,3> > elist;
std::vector<int> edges[1001];
int color[1001];
int sibling_index[1001];
int parent[1001];
int depth[1001];
std::vector<std::array<int,3> > at[1001];
int dp[1001][1<<20];
void dfs_tree(int node){
for(int i=0;i<edges[node].size();i++){
int child=edges[node][i];
edges[child].erase(std::find(edges[child].begin(),edges[child].end(),node));
color[child]=color[node]^1;
sibling_index[child]=i;
parent[child]=node;
depth[child]=depth[node]+1;
dfs_tree(child);
}
}
int lca(int x,int y){
if(depth[x]<depth[y]) std::swap(x,y);
while(depth[x]>depth[y]){
x=parent[x];
}
while(x!=y){
x=parent[x],y=parent[y];
}
return x;
}
void update(int node,int mask,int value){
for(int k=0;k<(1<<edges[node].size());k++){
if(k&mask) continue;
dp[node][k|mask]=std::max(dp[node][k|mask],dp[node][k]+value);
}
}
void dfs_solve(int node){
for(int i=0;i<edges[node].size();i++){
int child=edges[node][i];
dfs_solve(child);
update(node,1<<i,dp[child][(1<<edges[child].size())-1]);
}
for(auto e:at[node]){
//printf("at %d: %d<=>%d +%d\n",node,e[0],e[1],e[2]);
int value=0;
int master=0;
for(int c=0;c<2;c++){
int sibling=0;
for(int x=e[c];x!=node;sibling=1<<sibling_index[x],x=parent[x]){
value+=dp[x][(1<<edges[x].size())-1-sibling];
}
master|=sibling;
}
update(node,master,value+e[2]);
}
/*
for(int k=0;k<(1<<edges[node].size());k++){
printf("%d (%d): %d\n",node,k,dp[node][k]);
}
*/
}
int main(){
int N,M;
scanf("%d %d",&N,&M);
int total_cost=0;
for(int i=0;i<M;i++){
int A,B,C;
scanf("%d %d %d",&A,&B,&C);
A--,B--;
if(C==0){
edges[A].push_back(B);
edges[B].push_back(A);
}else{
elist.push_back({A,B,C});
total_cost+=C;
}
}
dfs_tree(0);
for(auto e:elist){
if(color[e[0]]==color[e[1]]){
at[lca(e[0],e[1])].push_back(e);
}
}
dfs_solve(0);
printf("%d\n",total_cost-dp[0][(1<<edges[0].size())-1]);
}
Compilation message
training.cpp: In function 'void dfs_tree(int)':
training.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<edges[node].size();i++){
~^~~~~~~~~~~~~~~~~~~
training.cpp: In function 'void dfs_solve(int)':
training.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<edges[node].size();i++){
~^~~~~~~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
~~~~~^~~~~~~~~~~~~~~
training.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&A,&B,&C);
~~~~~^~~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0x5f): relocation truncated to fit: R_X86_64_PC32 against symbol `__environ' defined in .bss section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(environ.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0x83): relocation truncated to fit: R_X86_64_PC32 against symbol `_dl_phdr' defined in COMMON section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(dl-support.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0xc7): relocation truncated to fit: R_X86_64_PC32 against symbol `_dl_phdr' defined in COMMON section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(dl-support.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0xd5): relocation truncated to fit: R_X86_64_PC32 against symbol `_dl_phnum' defined in COMMON section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(dl-support.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0x13e): relocation truncated to fit: R_X86_64_PC32 against symbol `_dl_osversion' defined in COMMON section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(dl-support.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0x14c): relocation truncated to fit: R_X86_64_PC32 against symbol `_dl_osversion' defined in COMMON section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(dl-support.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0x1a6): relocation truncated to fit: R_X86_64_PC32 against symbol `__environ' defined in .bss section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(environ.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0x1de): relocation truncated to fit: R_X86_64_PC32 against symbol `__environ' defined in .bss section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(environ.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `generic_start_main':
(.text+0x232): relocation truncated to fit: R_X86_64_PC32 against symbol `__environ' defined in .bss section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(environ.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `get_common_indeces.constprop.1':
(.text+0x2b0): relocation truncated to fit: R_X86_64_PC32 against symbol `_dl_x86_cpu_features' defined in .bss section in /usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(dl-support.o)
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/libc.a(libc-start.o): In function `get_common_indeces.constprop.1':
(.text+0x2b8): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
