제출 #372659

#제출 시각아이디문제언어결과실행 시간메모리
372659hivakarami구슬과 끈 (APIO14_beads)C++14
28 / 100
2 ms876 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define f first #define s second const int N = 200 + 100; const ll mod = 998244353; const ll inf = 1e9 + 100; ll dp[3][N], w[N][N], par[N]; vector<int> adj[N]; int n; void dfs(int u) { dp[1][u] = 0; for(auto x : adj[u]) { if(x != par[u]) { par[x] = u; dfs(x); dp[1][u] += min(dp[1][x] + w[x][u], dp[2][x]); } } dp[2][u] = inf; for(auto x : adj[u]) { if(x != par[u]) { ll mn = min(dp[1][x] + w[x][u], dp[2][x]); dp[2][u] = min(dp[2][u], dp[1][u] - mn + dp[1][x]); } } //cout << u << ' ' << dp[1][u] << ' ' << dp[2][u] << endl; } inline void cl() { for(int i = 0; i < n; i++) par[i] = i; } int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n; ll sum = 0; for(int i = 0; i < n-1; i++) { int x, y; cin >> x >> y; x--; y--; cin >> w[x][y]; adj[x].push_back(y); adj[y].push_back(x); w[y][x] = w[x][y]; sum += w[x][y]; } ll ans = inf; for(int i = 0; i < n; i++) { cl(); dfs(i); ans = min(ans, dp[1][i]); } cout << sum - ans << endl; 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...