记录编号	120	评测结果	AAATT
题目名称	公路建设	最终得分	30
用户昵称	cuixiaofei	是否通过	未通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-04-23 22:23:50	内存使用	0.01 MiB

//na                            :cuixiaofei;
//da                            :08_04_23;
program road;
  const
    city                        =550{550};
  type
    sss                         =record
                     x,y        :longint;
                     s          :real;
                                end;
  var
    n,m,ge,bian,x,y             :longint;
    he,s                        :real;
    ji                          :array[1..city,1..city] of real;
    pc                          :array[1..city] of longint;
    f1,f2                       :text;
  procedure quhuan(k:longint);
    var
      max                       :real;
      jiji                      :array[1..city,1..city] of longint;
      zg                        :longint;
      jin                       :array[1..city] of longint;
      panpan                    :longint;
    procedure sousuo(kkk:longint);
      var
        i                       :longint;
        panduan                 :longint;
      begin
        if panpan=1 then
          exit;
        if kkk=y then
          begin
            inc(zg);
            jin[zg]:=x;
            max:=0;
            for i:=1 to zg-1 do
              if ji[jin[i],jin[i+1]]>max then
              begin
                max:=ji[jin[i],jin[i+1]];
                panduan:=i;
              end;
            ji[jin[panduan],jin[panduan+1]]:=0;
            ji[jin[panduan+1],jin[panduan]]:=0;
            dec(bian);
            he:=he-max;
            panpan:=1;
            exit;
          end
        else
          begin
            for i:=1 to n do
              if (ji[kkk,i]>0) and (jiji[kkk,i]=0) and (((kkk<>x) or (i<>y)) and ((kkk<>y) or (i<>x))) then
              begin
                if panpan=1 then
                  exit;
                jiji[kkk,i]:=1;
                jiji[i,kkk]:=1;
                inc(zg);
                jin[zg]:=i;
                sousuo(i);
                dec(zg);
                jiji[kkk,i]:=0;
                jiji[i,kkk]:=0;
              end;
          end;
      end;
  begin
    fillchar(jiji,sizeof(jiji),0);
    panpan:=0;
    zg:=1;
    jin[zg]:=x;
    sousuo(x);
  end;

  procedure jinru(k:longint);
  begin
    if (ge=n) and (bian=n-2) and (ji[x,y]=0) then
      begin
        inc(bian);
        he:=he+s;
        ji[x,y]:=s;
        ji[y,x]:=s;
        inc(pc[x]);
        inc(pc[y]);
        writeln(f2,he/2:0:1);
        exit;
      end;
    if (pc[x]=0) and (pc[y]=0) then
      begin
        writeln(f2,0);
        he:=he+s;
        ji[x,y]:=s;
        ji[y,x]:=s;
        inc(ge,2);
        inc(bian);
        inc(pc[x]);
        inc(pc[y]);
        exit;
      end
    else if  (pc[x]>0) and (pc[y]>0) then
      begin
        he:=he+s;
        if ji[x,y]>0 then
          begin
            if ji[x,y]<s then
              begin
                he:=he-s;
              end
            else
              begin
                he:=he-ji[x,y];
                ji[x,y]:=s;
                ji[y,x]:=s;
              end;
          end
        else
          begin
            ji[x,y]:=s;
            ji[y,x]:=s;
            inc(bian);
            quhuan(k);
          end;
        if bian=n-1 then
          writeln(f2,he/2:0:1)
        else
          writeln(f2,0);
      end
    else
      begin
        inc(pc[x]);
        inc(pc[y]);
        ji[x,y]:=s;
        ji[y,x]:=s;
        he:=he+s;
        inc(ge);
        inc(bian);
        if bian=n-1 then
          writeln(f2,he/2:0:1)
        else
          writeln(f2,0);
      end;
  end;

  procedure init;
    var
      i                         :longint;
  begin
    fillchar(ji,sizeof(ji),0);
    bian:=0;
    assign(f1,'road.in');
    reset(f1);
    assign(f2,'road.out');
    rewrite(f2);
    ge:=0;
    he:=0;
    readln(f1,n,m);
    for i:=1 to m do
      begin
        x:=0;
        y:=0;
        s:=0;
        readln(f1,x,y,s);
        jinru(i);
      end;
    close(f2);
    close(f1);
  end;
  begin
    init;
  end.