记录编号	9835	评测结果	AAPAAAAAAA
题目名称	[AHOI2008] 上学路线	最终得分	92
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	0.972 s
提交时间	2009-04-21 17:42:15	内存使用	3.93 MiB

{
 haoi2009 moni1 t1 route
 time:2009.4.21
}
program cch(input,output);
const
 maxf=10000000;
var
 map,g,fc,ch:array[1..500,1..500] of longint;
 d,p:array[1..500] of longint;
 flow,n,m:longint;
 flag:array[1..500] of boolean;

procedure init;
var
 i,j,p,q,t,c:longint;
begin
 assign(input,'routez.in');
 assign(output,'routez.out');
 reset(input);
 rewrite(output);
 readln(n,m);
 for i:=1 to n do
  for j:=1 to n do
   map[i,j]:=maxf;
 for i:=1 to m do
  begin
   readln(p,q,t,c);
   if (map[p,q]>t) then
     begin
      map[p,q]:=t; map[q,p]:=t;
      fc[p,q]:=c; fc[q,p]:=c;
      ch[p,q]:=i; ch[q,p]:=i;
     end;
  end;
end;

procedure dijkstra;
var
 i,j,k,min:longint;
 flag:array[1..500] of boolean;
begin
 for i:=1 to n do d[i]:=map[1,i];
 for i:=1 to n do flag[i]:=true;
 d[1]:=0; flag[1]:=false;
 for i:=1 to n-1 do
  begin
   min:=maxf;
   for j:=1 to n do
    if flag[j] and (min>d[j]) then
     begin
      k:=j; min:=d[j];
     end;
   flag[k]:=false;
   for j:=1 to n do
    if flag[j] and (d[j]>d[k]+map[k,j]) then
     d[j]:=d[k]+map[k,j];
  end;
end;

procedure makeg;
var
 i,j:longint;
begin
 for i:=1 to n do
  for j:=1 to n do
   g[i,j]:=0;
 for i:=1 to n do
  for j:=1 to n do
   if (d[i]+map[i,j]=d[j]) then
     g[i,j]:=fc[i,j];
end;

procedure bfs;
var
 head,tail,i:longint;
 a:array[1..500] of longint;
begin
 head:=1; tail:=1;
 a[head]:=1;
 for i:=2 to n do p[i]:=-1; p[1]:=0;
 repeat
  for i:=1 to n do
   if (p[i]=-1)and(g[a[head],i]>0) then
    begin
     inc(tail);
     a[tail]:=i;
     p[i]:=p[a[head]]+1;
    end;
  inc(head);
 until head>tail;
end;

procedure dinic;
var
 l,k,i,tmp:longint;
 flag:boolean;
 last,stack:array[1..500] of integer;
begin
 flow:=0;
 while true do
  begin
   bfs;
   if p[n]=-1 then break;
   l:=1; stack[l]:=1;
   for i:=1 to n do last[i]:=0;
   while l<>0 do
    begin
     k:=stack[l];
     if k<>n then
      begin
       flag:=true;
       for i:=last[k]+1 to n do
        if (p[k]+1=p[i])and(g[k,i]>0) then
         begin
          inc(l); stack[l]:=i;
          last[k]:=i; flag:=false;
          break;
         end;
       if flag then
         begin
          p[k]:=-100; dec(l);
         end;
       end
      else
       begin
        k:=0;
        tmp:=maxlongint;
        for i:=2 to l do
         if tmp>g[stack[i-1],stack[i]] then
          tmp:=g[stack[i-1],stack[i]];
        flow:=flow+tmp;
        for i:=2 to l do
         begin
          dec(g[stack[i-1],stack[i]],tmp);
          inc(g[stack[i],stack[i-1]],tmp);
          if (k=0)and(g[stack[i-1],stack[i]]=0) then
           begin
            k:=stack[i-1]; l:=i-1;
           end;
         end;
       end;
      end;
   end;
end;

procedure dfs1(k:integer);
var
 i:integer;
begin
 flag[k]:=false;
 for i:=1 to n do
  if (g[k,i]>0)and flag[i] then
   dfs1(i);
end;

procedure getcut;
var
 i,j,ans2:longint;
 flag1:array[1..124750] of boolean;
begin
 for i:=1 to n do flag[i]:=true;
 for i:=1 to m do flag1[i]:=false;
 dfs1(1); ans2:=0;
 for i:=1 to n do
  for j:=1 to n do
   if (g[i,j]>0)and(flag[i])and(not flag[j]) then
    begin
     inc(ans2);
     flag1[ch[i,j]]:=true;
    end;
 write(ans2); writeln(' ',flow);
 for i:=1 to m do
  if flag1[i] then writeln(i);
end;

procedure main;
begin
 dijkstra;
 writeln(d[n]);
 makeg;
 dinic;
 getcut;
 close(input);
 close(output);
end;

begin
 init;
 main;
end.