记录编号	39314	评测结果	AAAAAAAAAA
题目名称	最小最大生成树	最终得分	100
用户昵称	zhangchi	是否通过	通过
代码语言	Pascal	运行时间	0.774 s
提交时间	2012-07-08 20:56:26	内存使用	17.94 MiB

type
  node=record
         v,c,next,un:longint;
       end;
var
  m,i,j,tot,s,t,flow,maxflow,totnum,ans:longint;
  found:boolean;
  f:array[1..20000] of longint;
  a:array[1..1000000] of node;
  h:array[1..20000] of longint;
  hnum:array[0..20000] of longint;
  v:array[1..3,0..200000] of longint;
  procedure insert(x,y,z:longint);
  begin
    inc(tot);
    a[tot].next:=f[x];
    f[x]:=tot;
    a[tot].v:=y;
    a[tot].c:=z;
    a[tot].un:=tot+1;
    inc(tot);
    a[tot].next:=f[y];
    f[y]:=tot;
    a[tot].v:=x;
    a[tot].c:=0;
    a[tot].un:=tot-1;
  end;
  procedure sap(x:longint);
  var
    p,temp,minh:longint;
  begin
    if x=t then
      begin
        inc(maxflow,flow);
        found:=true;
        exit;
      end;
    temp:=flow;
    minh:=totnum-1;
    p:=f[x];
    while p<>0 do
      begin
        if a[p].c>0 then
          begin
            if h[a[p].v]+1=h[x] then
              begin
                if a[p].c<flow then flow:=a[p].c;
                sap(a[p].v);
                if h[s]>=totnum then exit;
                if found then break;
                flow:=temp;
              end;
            if h[a[p].v]<minh then minh:=h[a[p].v];
          end;
        p:=a[p].next;
      end;
    if not found then
      begin
        dec(hnum[h[x]]);
        if hnum[h[x]]=0 then h[s]:=totnum;
        h[x]:=minh+1;
        inc(hnum[h[x]]);
      end
    else
      begin
        dec(a[p].c,flow);
        inc(a[a[p].un].c,flow);
      end;
  end;
begin
  assign(input,'mstmn.in'); reset(input);
  assign(output,'mstmn.out'); rewrite(output);
  readln(totnum,m);
  for i:=1 to m do
    readln(v[1,i],v[2,i],v[3,i]);
  readln(v[1,0],v[2,0],v[3,0]);
  //-------------------------
  tot:=0; s:=v[1,0]; t:=v[2,0];
  for i:=1 to m do
    if v[3,i]<v[3,0] then
      begin
        insert(v[1,i],v[2,i],1);
        insert(v[2,i],v[1,i],1);
      end;
  hnum[0]:=totnum;
  maxflow:=0;
  while h[s]<totnum do
    begin
      found:=false;
      flow:=maxlongint div 2;
      sap(s);
    end;
  ans:=ans+maxflow;
  //-------------------------
  tot:=0; s:=v[1,0]; t:=v[2,0];
  fillchar(a,sizeof(a),0);
  fillchar(f,sizeof(f),0);
  for i:=1 to m do
    if v[3,i]>v[3,0] then
      begin
        insert(v[1,i],v[2,i],1);
        insert(v[2,i],v[1,i],1);
      end;
  fillchar(h,sizeof(h),0);
  fillchar(hnum,sizeof(hnum),0);
  hnum[0]:=totnum;
  maxflow:=0;
  while h[s]<totnum do
    begin
      found:=false;
      flow:=maxlongint div 2;
      sap(s);
    end;
  ans:=ans+maxflow;
  writeln(ans);
  close(input); close(output);
end.