Submission #988425

#TimeUsernameProblemLanguageResultExecution timeMemory
988425huutuanTraining (IOI07_training)C++14
30 / 100
2 ms604 KiB
#include<bits/stdc++.h> using namespace std; const int N=1010, M=5010; int n, m, cnt, deg[N], dep[N], f[N]; vector<int> g[N]; vector<pair<int, int>> vv[N]; pair<pair<int, int>, int> edge[M]; void dfs(int u, int p){ dep[u]=dep[p]+1; for (int v:g[u]) if (v!=p) dfs(v, u); } 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]={{u, v}, w}, ans+=w; else g[u].push_back(v), g[v].push_back(u), ++deg[u], ++deg[v]; } int u=find(deg+1, deg+n+1, 1)-deg; dfs(u, 0); for (int i=1; i<=cnt; ++i) if ((dep[edge[i].first.first]&1)==(dep[edge[i].first.second]&1)){ int l=min(dep[edge[i].first.first], dep[edge[i].first.second]); int r=max(dep[edge[i].first.first], dep[edge[i].first.second])-1; vv[r].emplace_back(l, edge[i].second); } f[0]=0; for (int i=1; i<=n; ++i){ f[i]=max(f[i], f[i-1]); for (auto &j:vv[i]){ f[i]=max(f[i], f[j.first-1]+j.second); } } cout << ans-f[n] << '\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...