记录编号	39297	评测结果	AAAAAAAAAA
题目名称	最小最大生成树	最终得分	100
用户昵称	SnowDancer	是否通过	通过
代码语言	Pascal	运行时间	0.883 s
提交时间	2012-07-08 16:55:19	内存使用	14.97 MiB

program mstmn;
type
  flowedge=record
    v,c:longint;
    next,against:longint;
  end;
var
  n,i,j,k,l,m,s,t,value,flowtop,maxflow,minE,minH,arug,p:longint;
  flowedges:array[1..800008] of flowedge;
  u,v,e:array[1..200000] of longint;
  now,height,flowh,gap:array[0..20008] of longint;
  find:boolean;
function min(x,y:longint):longint;
  begin if x<y then exit(x) else exit(y); end;
procedure insertflowE(u,v,against,c:longint);
  begin
    flowedges[flowtop].v:=v;flowedges[flowtop].against:=against;
    flowedges[flowtop].next:=flowh[u]; flowh[u]:=flowtop;
    flowedges[flowtop].c:=c; inc(flowtop);
  end;
procedure SAP(k,delta:longint);
  var
    x:flowedge;
  begin
    if k=t then begin
      find:=true; arug:=delta;
      inc(maxflow,arug); exit;
    end;
    while now[k]<>0 do begin
      x:=flowedges[now[k]];
      if (height[x.v]+1=height[k]) and (x.c>0) then begin
        SAP(x.v,min(delta,x.c));
        if height[s]=n then exit;
        if find then break;
      end;
      now[k]:=x.next;
    end;
    if find then begin
      dec(flowedges[now[k]].c,arug);
      inc(flowedges[x.against].c,arug);
    end else begin
      minh:=n-1; p:=flowh[k]; minE:=p;
      while p<>0 do begin
        x:=flowedges[p];
        if (height[x.v]<minh) and (x.c>0) then begin
          minh:=height[x.v]; minE:=p;
        end;
        p:=x.next;
      end;
      dec(gap[height[k]]);
      if gap[height[k]]=0 then height[s]:=n;
      inc(gap[minh+1]);
      height[k]:=minh+1; now[k]:=minE;
    end;
  end;
begin
  //  OpenFile
  assign(input,'mstmn.in');   reset(input);
  assign(output,'mstmn.out'); rewrite(output);
  //  Input
  readln(n,m);
  for l:=1 to m do
    readln(u[l],v[l],e[l]);
  readln(s,t,value);
  //  CalMinST
  flowtop:=1;
  for i:=1 to m do
    if e[i]>value then begin
      insertflowE(u[i],v[i],flowtop+1,1);
      insertflowE(v[i],u[i],flowtop-1,0);
      insertflowE(v[i],u[i],flowtop+1,1);
      insertflowE(u[i],v[i],flowtop-1,0);
    end;
  gap[0]:=n; now:=flowh;
  repeat
    find:=false;
    SAP(s,maxlongint);
  until height[s]=n;
  //  CalMaxST
  fillchar(height,sizeof(height),0);
  fillchar(gap,sizeof(height),0);
  fillchar(flowh,sizeof(flowh),0);
  fillchar(flowedges,sizeof(flowedges),0);
  flowtop:=1;
  for i:=1 to m do
    if e[i]<value then begin
      insertflowE(u[i],v[i],flowtop+1,1);
      insertflowE(v[i],u[i],flowtop-1,0);
      insertflowE(v[i],u[i],flowtop+1,1);
      insertflowE(u[i],v[i],flowtop-1,0);
    end;
  gap[0]:=n; now:=flowh;
  repeat
    find:=false;
    SAP(s,maxlongint);
  until height[s]=n;
  //  Print
  writeln(maxflow);
  //  CloseFile
  close(input); close(output);
end.