Hướng dẫn giải của 2 xe ủi


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.