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

type
 point=^node;
 node=record
  data,w:longint;
  next,opp:point;
 end;
var
 i,j,k,m,n,u,v,l,ans,delt:longint;
 x,y,ww:array[1..200000]of longint;
 c,d:array[1..20000]of point;
 h,gap:array[0..20000]of longint;
 p,f:point;
 flag:boolean;

 function min(a,b:longint):longint;
 begin if a<b then exit(a) else exit(b);end;
 
 procedure sap(x:longint);
 var k,pp,minh:longint;  p:point;
 begin
   if x=v then begin 
	 inc(ans,delt);
     flag:=true;exit;  
   end ;	   
   minh:=n-1;
   p:=c[x];
   pp:=delt;
   while p<>nil do 
	 begin
       if p^.w>0 then 
		begin    
		if h[x]=h[p^.data]+1 then 
			   begin
		          k:=p^.data;
		          delt:=min(delt,p^.w);
		          sap(k);
				  if h[u]>=n then exit;	  
		          if flag then break;
				  delt:=pp;
			   end ;
		minh:=min(minh,h[p^.data]);
		end;		  
	    p:=p^.next;
     end ;  
				  
	if flag then begin
		dec(p^.w,delt);inc(p^.opp^.w,delt);
	end else begin
		dec(gap[h[x]]);
	    if gap[h[x]]=0 then h[u]:=n;
		h[x]:=minh+1;inc(gap[h[x]]);	
	end;	
 end;

begin
assign(input,'mstmn.in');reset(input);
assign(output,'mstmn.out');rewrite(output);		
 readln(n,m);
 for i:=1 to m do read(x[i],y[i],ww[i]);
 read(u,v,l);
 
 for i:=1 to m do 
  begin
    if ww[i]>l then  begin 
      new(p);p^.data:=y[i];p^.w:=1;
      p^.next:=d[x[i]];d[x[i]]:=p;
	  new(f);f^.data:=x[i];f^.w:=1;
      f^.next:=d[y[i]];d[y[i]]:=f;
	  f^.opp:=p;p^.opp:=f;
   end else if ww[i]<l then begin 
	  new(p);p^.data:=x[i];p^.w:=1;
      p^.next:=c[y[i]];c[y[i]]:=p;
      new(f);f^.data:=y[i];f^.w:=1;
      f^.next:=c[x[i]];c[x[i]]:=f;
      f^.opp:=p;p^.opp:=f;
   end;
  end;  //writeln('fafdsa');halt;
                         {for i:=1 to n do 
							 begin
						     p:=c[i];
							while p<>nil do 
								 begin write(p^.data,' ',p^.opp^.data,' s');p:=p^.next;end;
						    writeln;
							end ;halt;}
   ans:=0;
   fillchar(h,sizeof(h),0);
   fillchar(gap,sizeof(gap),0);
   gap[0]:=n;
   while h[u]<n do 
	 begin flag:=false;delt:=maxlongint;sap(u);end;
   
   fillchar(h,sizeof(h),0);
   fillchar(gap,sizeof(gap),0);
   c:=d;gap[0]:=n;
   while h[u]<n do 
	 begin flag:=false;delt:=maxlongint;sap(u);end; 
   writeln(ans);
 close(input);close(output);  
end.