Submission #988494

#TimeUsernameProblemLanguageResultExecution timeMemory
988494huutuanTraining (IOI07_training)C++14
100 / 100
9 ms4952 KiB
#include<bits/stdc++.h> using namespace std; const int N=1010, M=5010; int n, m, cnt_edge, dep[N], f[N][1024], par[N]; vector<int> g[N]; vector<int> vv[N]; pair<pair<int, int>, int> edge[M]; void pre_dfs(int u, int p){ dep[u]=dep[p]+1; par[u]=p; if (p) g[u].erase(find(g[u].begin(), g[u].end(), p)); for (int v:g[u]) pre_dfs(v, u); } int lca(int u, int v){ if (dep[u]>dep[v]) swap(u, v); while (dep[u]!=dep[v]){ v=par[v]; } while (u!=v){ u=par[u]; v=par[v]; } return u; } int idx[N], cnt[N]; void dfs(int u){ for (int v:g[u]) dfs(v); cnt[u]=(int)g[u].size(); for (int i=0; i<cnt[u]; ++i) idx[g[u][i]]=i; for (int i=0; i<cnt[u]; ++i) f[u][1<<i]=f[g[u][i]][(1<<cnt[g[u][i]])-1]; for (int _:vv[u]){ int v1=edge[_].first.first, v2=edge[_].first.second, w=edge[_].second; if (v2==u) swap(v1, v2); if (v1==u){ int sum=0, lst=-1; while (v2!=u){ if (lst==-1) sum+=f[v2][(1<<cnt[v2])-1]; else sum+=f[v2][((1<<cnt[v2])-1)^(1<<idx[lst])]; lst=v2; v2=par[v2]; } f[u][1<<idx[lst]]=max(f[u][1<<idx[lst]], sum+w); }else{ int sum=0, lst1=-1, lst2=-1; while (v1!=u){ if (lst1==-1) sum+=f[v1][(1<<cnt[v1])-1]; else sum+=f[v1][((1<<cnt[v1])-1)^(1<<idx[lst1])]; lst1=v1; v1=par[v1]; } while (v2!=u){ if (lst2==-1) sum+=f[v2][(1<<cnt[v2])-1]; else sum+=f[v2][((1<<cnt[v2])-1)^(1<<idx[lst2])]; lst2=v2; v2=par[v2]; } f[u][(1<<idx[lst1])|(1<<idx[lst2])]=max(f[u][(1<<idx[lst1])|(1<<idx[lst2])], sum+w); } } for (int i=0; i<(1<<cnt[u]); ++i){ for (int j=(i-1)&i; ; j=(j-1)&i){ f[u][i]=max(f[u][i], f[u][j]+f[u][i^j]); if (!j) break; } } } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; int ans=0; for (int i=1; i<=m; ++i){ int u, v, w; cin >> u >> v >> w; if (w) edge[++cnt_edge]={{u, v}, w}, ans+=w; else g[u].push_back(v), g[v].push_back(u); } pre_dfs(1, 0); for (int i=1; i<=cnt_edge; ++i) if ((dep[edge[i].first.first]&1)==(dep[edge[i].first.second]&1)){ vv[lca(edge[i].first.first, edge[i].first.second)].push_back(i); } dfs(1); cout << ans-f[1][(1<<cnt[1])-1] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...