Editorial for 2 xe ủi
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; maxn=100010; var n,s,re,r1,r2,same,max:longint; a,b:array[1..maxn shl 1] of longint; pos,cur,sl,d,f,g,m1,m2:array[1..maxn] of longint; c:array[1..maxn,0..2] of longint; procedure rf; var i,p,q:longint; begin assign(input,fi); reset(input); readln(n,s); for i:=1 to n-1 do begin read(c[i,0],c[i,1],c[i,2]); inc(sl[c[i,0]]); inc(sl[c[i,1]]); end; pos[1]:=1; cur[1]:=1; for i:=2 to n+1 do begin pos[i]:=pos[i-1]+sl[i-1]; cur[i]:=pos[i]; end; for i:=1 to n-1 do begin p:=c[i,0]; q:=c[i,1]; a[cur[p]]:=q; a[cur[q]]:=p; b[cur[p]]:=c[i,2]; b[cur[q]]:=c[i,2]; inc(cur[p]); inc(cur[q]); end; close(input); end; procedure dfs(x,y:longint); var i,v:longint; begin for i:=pos[x] to pos[x+1]-1 do if a[i]=y then begin f[x]:=b[i]; break; end; d[x]:=1; for i:=pos[x] to pos[x+1]-1 do if d[a[i]]=0 then begin dfs(a[i],x); f[x]:=f[x]+f[a[i]]+b[i]; v:=m1[a[i]]+b[i]; if v>=m1[x] then begin m2[x]:=m1[x]; m1[x]:=v; end else begin if v>m2[x] then m2[x]:=v; end; if m1[x]+m2[x]>max then max:=m1[x]+m2[x]; end; end; procedure pr; var i,j:longint; begin dfs(s,0); re:=f[s]-max; end; procedure wf; begin assign(output,fo); rewrite(output); writeln(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của ladpro98
#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <cstring> #define FOR(i, a, b) for(int i=(a); i< (b); i++) #define REP(i, a, b) for(int i=(a); i<=(b); i++) #define ii pair<int, int> #define X first #define Y second const int N = 100005; using namespace std; vector<ii> a[N], child[N]; bool was[N]; int n, root; int F[N][2][2]; void Init(int u) { was[u] = true; FOR(i, 0, a[u].size()) { int v = a[u][i].X; if (!was[v]) { Init(v); child[u].push_back(ii(v, a[u][i].Y)); } } a[u] = child[u]; } int DP(int u, int bull, int ret) { if (F[u][bull][ret] >= 0) return F[u][bull][ret]; #define v a[u][i] if (bull == 1) { if (ret == 1) { F[u][1][1] = 0; FOR(i, 0, a[u].size()) F[u][1][1] += DP(v.X, 1, 1) + 2 * v.Y; } else { F[u][1][0] = DP(u, 1, 1); FOR(i, 0, a[u].size()) F[u][1][0] = min(F[u][1][0], F[u][1][1] - v.Y - DP(v.X, 1, 1) + DP(v.X, 1, 0)); } } else { F[u][2][0] = DP(u, 1, 1); FOR(i, 0, a[u].size()) F[u][2][0] = min(F[u][2][0], F[u][1][1] - DP(v.X, 1, 1) + DP(v.X, 2, 0)); vector<int> P; FOR(i, 0, a[u].size()) P.push_back(DP(v.X, 1, 0) - v.Y - DP(v.X, 1, 1)); sort(P.begin(), P.end()); if (P.size() > 1) F[u][2][0] = min(F[u][2][0], F[u][1][1] + P[0] + P[1]); } #undef v //cout << u << ' ' << bull << ' ' << ret << ' ' << F[u][bull][ret] << endl; return F[u][bull][ret]; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> root; int u, v, c; FOR(i, 1, n) { cin >> u >> v >> c; a[u].push_back(ii(v, c)); a[v].push_back(ii(u, c)); } Init(root); memset(F, 255, sizeof F); cout << DP(root, 2, 0); return 0; }
Code mẫu của RR
//Written by RR {$MODE OBJFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 100111; type list = ^node; node = record u,c : longint; next : list; end; procedure add(u,c:longint; var a:list); inline; var p:list; begin new(p); p^.u:=u; p^.c:=c; p^.next:=a; a:=p; end; var f1,f2 : text; n : longint; ke : array[1..MAXN] of list; f,father : array[1..MAXN] of longint; res : longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i,u,v,c:longint; begin read(f1,n,c); for i:=1 to n-1 do begin read(f1,u,v,c); add(u,c,ke[v]); add(v,c,ke[u]); end; end; procedure dfs(u:longint); var p:list; v,c,m1,m2,now:longint; begin f[u]:=0; p:=ke[u]; m1:=0; m2:=0; while p<>nil do begin v:=p^.u; c:=p^.c; p:=p^.next; if v=father[u] then continue; if f[v]=-1 then begin father[v]:=u; dfs(v); end; now:=f[v]+c; if now>m1 then begin m2:=m1; m1:=now; end else if now>m2 then m2:=now; end; f[u]:=m1; res:=max(res,m1+m2); end; procedure solve; var i:longint; p:list; begin res:=0; fillchar(f,sizeof(f),$FF); dfs(1); res:=-res; for i:=1 to n do begin p:=ke[i]; while p<>nil do begin inc(res,p^.c); p:=p^.next; end; end; writeln(f2,res); end; begin openF; inp; if n=1 then writeln(f2,0) else solve; closeF; end.
Code mẫu của khuc_tuan
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> using namespace std; int n, x; vector<pair<int,int> > ke[100010]; int h[100010]; void dfs(int i, int fi) { for(int k=0;k<ke[i].size();++k) { int j = ke[i][k].first; if(j != fi) { h[j] = h[i] + ke[i][k].second; dfs(j, i); } } } int main() { int total = 0; scanf("%d%d", &n, &x); for(int i=1;i<n;++i) { int u, v, c; scanf("%d%d%d", &u, &v, &c); total += c; ke[u].push_back(make_pair(v,c)); ke[v].push_back(make_pair(u,c)); } dfs(1, -1); int imax = max_element( h + 1, h + 1 + n) - h; h[imax] = 0; dfs(imax, -1); imax = max_element( h + 1, h + 1 + n) - h; printf("%d\n", total * 2 - h[imax]); return 0; }
Comments