bzoj1937

这道题没弄明白

初始模型很好想，是用到了最小生成树的性质

加入非树边后树上形成的环，非树边一定大于等于任意树边

然后考虑树边一定是缩小，非树边一定是增大

有di+wi>=dj-wj wi+wj>=dj-di（j是加入i形成的环上的边）

然后不知道为什么求∑wi最小就是跑最大费用可行流

求神犇指教

type node=record
       po,next,cost,flow:longint;
     end;

var e:array[0..2000010] of node;
    v,f:array[0..810] of boolean;
    a:array[0..60,0..60] of longint;
    d,pre,cur,w,p:array[0..810] of longint;
    q:array[0..2000010] of longint;
    x,y,len,i,j,n,m,t,k:longint;

procedure add(x,y,f,c:longint);
  begin
    inc(len);
    e[len].po:=y;
    e[len].next:=p[x];
    e[len].cost:=c;
    e[len].flow:=f;
    p[x]:=len;
  end;

procedure build(x,y,f,c:longint);
  begin
    add(x,y,f,c);
    add(y,x,0,-c);
  end;

function dfs(x:longint):boolean;
  var i:longint;
  begin
    f[x]:=true;
    if x=j then
    begin
      q[0]:=-1;
      exit;
    end;
    for i:=1 to n do
      if not f[i] and v[a[x,i]] then
      begin
        inc(t);
        q[t]:=a[x,i];
        dfs(i);
        if q[0]=-1 then exit;
        q[t]:=0;
        dec(t);
      end;
  end;

function spfa:boolean;
  var f,r,y,i,j,x:longint;
  begin
    f:=1;
    r:=1;
    q[1]:=0;
    d[0]:=0;
    for i:=1 to t do
      d[i]:=-1000007;
    fillchar(v,sizeof(v),false);
    while f<=r do
    begin
      x:=q[f];
      v[x]:=false;
      i:=p[x];
      while i<>-1 do
      begin
        y:=e[i].po;
        if e[i].flow>0 then
          if d[y]<d[x]+e[i].cost then
          begin
            d[y]:=d[x]+e[i].cost;
            pre[y]:=x;
            cur[y]:=i;
            if not v[y] then
            begin
              v[y]:=true;
              inc(r);
              q[r]:=y;
            end;
          end;
        i:=e[i].next;
      end;
      inc(f);
    end;
    if d[t]>=0 then exit(true) else exit(false);
  end;

function maxcost:longint;
  var i,j:longint;
  begin
    maxcost:=0;
    while spfa do
    begin
      i:=t;
      while i<>0 do
      begin
        j:=cur[i];
        dec(e[j].flow);
        inc(e[j xor 1].flow);
        i:=pre[i];
      end;
      maxcost:=maxcost+d[t];
    end;
  end;

begin
  len:=-1;
  fillchar(p,sizeof(p),255);
  readln(n,m);
  for i:=1 to m do
  begin
    readln(x,y,w[i]);
    a[x,y]:=i;
    a[y,x]:=i;
  end;
  for i:=1 to n-1 do
  begin
    readln(x,y);
    k:=a[x,y];
    v[k]:=true;
    build(0,k,1,0);
  end;
  for i:=1 to n do
    for j:=i+1 to n do
      if (a[i,j]>0) and not v[a[i,j]] then
      begin
        build(a[i,j],m+1,1,0);
        fillchar(f,sizeof(f),false);
        t:=0; q[0]:=0;
        dfs(i);
        for k:=1 to t do
          if w[q[k]]>w[a[i,j]] then build(q[k],a[i,j],1,w[q[k]]-w[a[i,j]]);
      end;
  t:=m+1;
  writeln(maxcost);
end.