记录编号	24950	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] 晨跑	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	1.761 s
提交时间	2011-05-26 12:09:51	内存使用	1.33 MiB

program chenpao;
var
  a,b,c,n,m,i,money,f:longint;
  g,cost:array[1..400,1..400]of longint;
  d,last,min:array[1..400]of longint;
procedure spfa;
var
  i,t,w,k:longint;
  bz:array[1..400]of boolean;
  team:array[1..10000]of longint;
begin
  fillchar(team,sizeof(team),0);
  for i:=1 to 2*n do
  begin  
    d[i]:=maxlongint;
    bz[i]:=true;
  end;
  fillchar(last,sizeof(last),0);
  fillchar(min,sizeof(min),0);
  t:=1;
  w:=1;
  team[1]:=1;
  min[1]:=maxlongint;
  d[1]:=0;
  bz[1]:=false;
  while t<=w do
  begin
    k:=team[t];
    bz[k]:=true;
    t:=t+1;
    for i:=1 to 2*n do
    begin
      if (g[k,i]>0)and(d[k]+cost[k,i]<d[i]) then
      begin
        if min[k]<g[k,i] then
          min[i]:=min[k]
        else
          min[i]:=g[k,i];
        d[i]:=d[k]+cost[k,i];
        last[i]:=k;
        if bz[i] then
        begin
          w:=w+1;
          team[w]:=i;
          bz[i]:=false
        end
      end
    end
  end
end;
procedure zg;
var
  z,t:longint;
begin
  z:=min[n];
  t:=n;
  repeat 
    dec(g[last[t],t],z);
    if g[last[t],t]=0 then
    begin
      if last[t]=1 then
      begin
        inc(money,z*cost[last[t],t]);
        cost[1,t]:=maxlongint
      end
      else
        if t=n then
        begin
          inc(money,z*cost[last[t],t]);
          cost[last[t],n]:=maxlongint
        end
        else
        begin
          inc(money,z*cost[last[t],t]);
          inc(g[t,last[t]],z);
          cost[t,last[t]]:=-cost[last[t],t]
        end
    end
    else
      inc(money,z*cost[last[t],t]);
    t:=last[t]
  until t=1;
  inc(f,z)
end;
procedure init;
begin
  readln (n,m);
  for i:=2 to n-1 do
    g[i,i+n]:=1;
  for i:=1 to m do
  begin
    readln (a,b,c);
    if a=1 then
    begin
      g[a,b]:=1;
      cost[a,b]:=c
    end
    else
    begin  
      g[n+a,b]:=1;
      cost[n+a,b]:=c
    end
  end
end;
procedure work;
begin
  spfa;
  while d[n]<>maxlongint do
  begin
    zg;
    spfa 
  end
end;
procedure print;
begin
  writeln (f,' ',money)
end;
begin
  assign (input,'run.in');
  reset (input);
  assign (output,'run.out');
  rewrite (output);
    init;
    work;
    print;
  close (input);
  close (output)
end.