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

program mstmn;
type
  integer=longint;
  edges=record st,en,w:integer; end;
const
  maxn=21000;
  maxm=210000;
  INF=10000000;
var
  n,m:integer;
  s,t,tot,L:integer;
  edge:array[1..maxm] of edges;
  ver,current:array[1..maxn] of integer;
  en,next:array[1..maxm shl 2] of integer;
  Cap,Flow:array[1..maxm shl 2] of integer;
  level:array[1..maxn] of integer;
  Q:array[1..maxn] of integer;

  procedure Fopen;
  begin
    assign(input,'mstmn.in'); reset(input);
    assign(output,'mstmn.out'); rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input); close(output);
  end;

  procedure Init;
  var
    i:integer;
  begin
    readln(n,m);
    for i:=1 to m do readln(edge[i].st,edge[i].en,edge[i].w);
    readln(s,t,L);
  end;

  procedure addedge(u,v,c:integer);
  begin
    inc(tot);
    en[tot]:=v; next[tot]:=ver[u]; ver[u]:=tot;
    Cap[tot]:=c;
  end;

  function BFS:boolean;
  var
    head,tail:integer;
    k,x,y:integer;
  begin
    fillchar(level,sizeof(level),0);
    level[s]:=1;
    head:=1; tail:=2;
    Q[1]:=s;
    repeat
      x:=Q[head];
      k:=ver[x];
      while k>0 do
      begin
        y:=en[k];
        if (Cap[k]>Flow[k]) and (level[y]=0) then
        begin
          level[y]:=level[x]+1;
          if y=t then exit(true);
          Q[tail]:=y;
          inc(tail);
        end;
        k:=next[k];
      end;
      inc(head);
    until head=tail;
    exit(level[t]>0);
  end;

  function min(a,b:integer):integer;
  begin
    if a<b then exit(a) else exit(b);
  end;

  function DFS(u,cur:integer):integer;
  var
    f,delta:integer;
    k,v:integer;
  begin
    if u=t then exit(cur);
    f:=cur;
    k:=current[u];
    while k>0 do
    begin
      v:=en[k];
      if (Cap[k]>Flow[k]) and (level[u]+1=level[v]) then
      begin
        delta:=DFS(v,min(f,Cap[k]-Flow[k]));
        inc(Flow[k],delta);
        dec(Flow[k xor 1],delta);
        dec(f,delta);
        if f=0 then break;
      end;
      k:=next[k];
    end;
    current[u]:=k;
    exit(cur-f);
  end;

  function Dinic:integer;
  var
    maxflow,delta:integer;
  begin
    fillchar(Flow,sizeof(Flow),0);
    maxflow:=0;
    while BFS do
      repeat
        current:=ver;
        delta:=DFS(s,INF);
        inc(maxflow,delta);
      until delta=0;
    exit(maxflow);
  end;

  procedure Solve;
  var
    i:integer;
    ans:integer;
  begin
    ans:=0;
    fillchar(ver,sizeof(ver),0);
    fillchar(next,sizeof(next),0);
    tot:=1;
    for i:=1 to m do if edge[i].w<L then
    begin
      addedge(edge[i].st,edge[i].en,1);
      addedge(edge[i].en,edge[i].st,0);
      addedge(edge[i].en,edge[i].st,1);
      addedge(edge[i].st,edge[i].en,0);
    end;
    ans:=ans+Dinic;
    fillchar(ver,sizeof(ver),0);
    fillchar(next,sizeof(next),0);
    tot:=1;
    for i:=1 to m do if edge[i].w>L then
    begin
      addedge(edge[i].st,edge[i].en,1);
      addedge(edge[i].en,edge[i].st,0);
      addedge(edge[i].en,edge[i].st,1);
      addedge(edge[i].st,edge[i].en,0);
    end;
    ans:=ans+Dinic;
    writeln(ans);
  end;

begin
  Fopen;
  Init;
  Solve;
  Fclose;
end.