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

type pa=^pb;
pb=record
 d,w:longint;
 ag,n:pa;
end;
var
 x,y,l:array[1..200000] of longint;
 a:array[1..20011] of pa;
 h,vh:array[0..20011] of longint;
 n,m,i,j,xx,yy,ll,s,t,mf,f:longint;
 o:boolean;
 procedure add(x,y,z:longint);
 var px,py:pa;
 begin
  new(px);
  px^.d:=z;
  px^.w:=y;
  px^.n:=a[x];
  a[x]:=px;
  new(py);
  py^.d:=z;
  py^.w:=x;
  py^.n:=a[y];
  a[y]:=py;
  a[x]^.ag:=a[y];
  a[y]^.ag:=a[x];
 end;
 procedure dfs(k:longint);
 var p,mh,i:longint;  pt:pa;
 begin
 p:=mf;
 mh:=n-1;
 if k=t then begin inc(f,mf);o:=true; exit; end;
 pt:=a[k];
  while pt<>nil do
  begin
  i:=pt^.w;
  if pt^.d>0 then
   begin
    if h[i]+1=h[k] then
     begin
      if mf>pt^.d then mf:=pt^.d;
      dfs(i);
      if h[s]>=n then exit;
      if o then break;
      mf:=p;
     end;
   if h[i]<mh then mh:=h[i];
   end;
   pt:=pt^.n;
  end;
  if not o then
   begin
    dec(vh[h[k]]);
    if vh[h[k]]=0 then h[s]:=n;
    h[k]:=mh+1;
    inc(vh[h[k]]);
   end else begin
   dec(pt^.d,mf);
   inc(pt^.ag^.d,mf);
   end;
 end;
begin
assign(input,'mstmn.in');reset(input);
assign(output,'mstmn.out');rewrite(output);
 readln(n,m);
 for i:=1 to  m do readln(x[i],y[i],l[i]);
 readln(xx,yy,ll);
 for i:=1 to m do
   if l[i]<ll then
    add(x[i],y[i],1);
 s:=xx;t:=yy;f:=0;
 vh[0]:=n;
 while h[s]<n do
  begin
   o:=false;
   mf:=maxlongint;
   dfs(s);
  end;
  for i:=1 to n do a[i]:=nil;
  for i:=1 to m do
   if l[i]>ll then
    add(x[i],y[i],1);
 s:=xx;t:=yy;
 fillchar(h,sizeof(h),0);
 fillchar(vh,sizeof(vh),0);
 vh[0]:=n;
 while h[s]<n do
  begin
   o:=false;
   mf:=maxlongint;
   dfs(s);
  end;
 writeln(f);
 close(input);close(output);
end.