记录编号	9809	评测结果	PPPPPPPTTT
题目名称	[AHOI2008] 上学路线	最终得分	13
用户昵称	lc	是否通过	未通过
代码语言	Pascal	运行时间	3.062 s
提交时间	2009-04-21 11:42:06	内存使用	7.99 MiB

program ex3;
  const
    maxn=500;
    maxm=maxn*maxn;
 var
      n,m:      longint;
      maxflow:  longint;
      s,t:      longint;
      ans:      array[0..maxm] of longint;
      fa:       array[1..500,0..500] of longint;
      mark:     array[1..maxn] of boolean;
      visit:    array[1..maxn,1..maxn] of boolean;
      bian:     array[1..maxn,0..maxn] of longint;
      bi:       array[1..maxn*maxn] of record
                xx,yy,cc:longint;
                end;
      g,cost:   array[1..maxn,1..maxn] of longint;
      od,last,q,lable:        array[1..maxn] of longint;


 function min(a,b:longint):longint;

   begin
     if a<b then exit(a) else exit(b);
   end;


 procedure Init;
   var
        i,j,x,y,t,c:    longint;
   begin
     readln(n,m);
     fillchar(g,sizeof(g),$FF);
     for i :=1 to m do begin
         readln(x,y,t,c);
         g[x,y] :=t; g[y,x] :=t;
         inc(bian[x,0]); bian[x,bian[x,0]]:=y;
         with bi[i] do begin xx:=x; yy:=y; cc :=c; end;
         end;
   end;

 procedure print(v:longint);
   var
       i:       longint;
   begin
     for i :=1 to fa[v,0] do begin
         print(fa[v,i]);
         visit[fa[v,i],v] :=true;
         end;
   end;


 procedure Dijkstra(v0:longint);
   var
       i,j,k,min:   longint;
       dis:     array[1..maxn] of longint;
   begin
     for i :=1 to n do dis[i] :=maxlongint;
     dis[v0]:=0;
     for i :=1 to n-1 do begin
         min :=maxlongint;
         for j :=1 to n do if (not mark[j])  and (dis[j]<min)
             then begin min :=dis[j]; k :=j end;
         mark[k] :=true;
         for j :=1 to n do if g[k,j]<>-1 then
             if dis[k]+g[k,j]<dis[j] then begin
                dis[j] :=dis[k]+g[k,j];
                fa[j,0] :=1; fa[j,1]:=k;
                end
             else if dis[k]+g[k,j]=dis[j]
                  then begin inc(fa[j,0]); fa[j,fa[j,0]]:=k end;
         end;
     writeln(dis[n]);
     print(n);
   end;

 procedure BFs;
   var
      head,tail,u,i:    longint;
   begin
     fillchar(od,sizeof(od),0);
     fillchar(lable,sizeof(lable),$FF);
     head :=1; tail :=1; q[1] :=s;   lable[s] :=0;
     repeat
       u :=q[head];
       for i :=1 to n do if cost[u,i] > 0 then
           begin
           if (lable[i] = -1 )  or (lable[i]=lable[u]+1)
              then begin
                   if lable[i]=-1 then begin inc(tail); q[tail] :=i; end;
                   lable[i] :=lable[u]+1;
                   inc(od[u]);
                   end;
           end;
       inc(head);
     until head > tail;
   end;

 procedure DFs;
   var
       top,u,i,r:     longint;
   begin
     top :=1; q[top] :=s;
     fillchar(last,sizeof(last),0);
     while top > 0 do begin
       u :=q[top];
       if u <> t then begin
                 if od[u] > 0 then begin
                              for i :=last[u]+1 to n do if cost[u,i] > 0
                                  then if lable[i]=lable[u]+1
                                       then begin
                                            inc(top); q[top] :=i;
                                            last[u] :=i; dec(od[u]);
                                            break;
                                            end;
                              end
                    else begin
                         q[top] :=0; dec(top);
                         end;
                 end
       else begin
             r :=maxlongint;
             for i :=1 to top-1 do r :=min(r,cost[q[i],q[i+1]]);
             for i :=1 to top-1 do begin
                 inc(cost[q[i+1],q[i]],r);
                 dec(cost[q[i],q[i+1]],r);
                 end;
             inc(maxflow,r);
             i :=1; while cost[q[i],q[i+1]]>0 do inc(i); top :=i;
            end;
       end;
   end;


 procedure Dinic;

   begin
     s :=1;  t :=n;
     repeat
       BFs; if lable[t] = -1 then break;
       DFs;
     until false;
   end;

 procedure search(v:longint);
   var
      i:        longint;
   begin
     if mark[v] then exit;
     mark[v] :=true;
     for i :=1 to n do if cost[v,i] > 0
         then search(i);
   end;

 procedure Main;
   var
        i:      longint;
   begin
     Dijkstra(1);
     for i :=1 to m do if visit[bi[i].xx,bi[i].yy]
         then cost[bi[i].xx,bi[i].yy] :=bi[i].cc;
     Dinic;
     fillchar(mark,sizeof(mark),0);
     search(s);
     for i :=1 to m do if visit[bi[i].xx,bi[i].yy]
         then if  mark[bi[i].xx] and not mark[bi[i].yy]
              then begin
                   inc(ans[0]);
                   ans[ans[0]]:=i;
                   end;
     write(ans[0],' ',maxflow,' ');
     for i :=1 to ans[0]-1 do write(ans[i],' ');
     writeln(ans[ans[0]]);
   end;

 begin
   assign(input,'routez.in'); reset(input);
   assign(output,'routez.out'); rewrite(output);
   Init;
   Main;
   close(input); close(output);
 end.