记录编号	10046	评测结果	AAAAAAAAAA
题目名称	K- 联赛	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	Pascal	运行时间	0.934 s
提交时间	2009-04-24 15:41:48	内存使用	2.57 MiB

program day3_3;
 const
   maxn = 25;
   maxT = 800;
   Inf =100000000;
 var
     n,NN:         longint;
     maxflow,maxwi:   longint;
     S,T:       longint;
     btot,totmatch,sumleft:  longint;
     a:         array[1..maxn,1..maxn] of longint;
     w,f:       array[1..maxn] of longint;
     cost:      array[1..maxT,1..maxT] of longint;
     lable,last,q,ww:      array[1..maxT] of longint;
     ans:       array[0..maxn] of longint;


 procedure Init;
   var
        i,j:      longint;
   begin
     readln(n);
     for i :=1 to n do read(w[i],f[i]);
     for i :=1 to n do if w[i]>maxwi then maxwi :=w[i];
     for i :=1 to n do
         for j :=1 to n do read(a[i,j]);
     for i :=1 to n do
         for j :=i+1 to n do inc(totmatch,a[i,j]);
   end;


 procedure make_graph;
   var
        i,j:    longint;
   begin
     btot :=n;
     for i :=1 to n do
         for j :=i+1 to n do if a[i,j] > 0
             then begin
             inc(btot);
             cost[btot,i] :=a[i,j];               //Ei-->i
             cost[btot,j] :=a[i,j];               //Ei-->j
             ww[btot] :=a[i,j]
             end;
     S :=btot+1; T :=btot+2;
     for i :=n+1 to btot do cost[S,i] :=ww[i];       //S-->Ei
     for i :=1 to n do cost[i,T] :=sumleft - w[i];   //i-->T
     NN :=btot+2;
   end;

 function BFs :boolean;
   var
        head,tail,u,i:    longint;

   begin
     fillchar(lable,sizeof(lable),$FF);
     head :=1; tail :=1; q[1] :=S;  lable[S] :=0;
     repeat
       u :=q[head];
       for i :=1 to NN do if cost[u,i] >0
           then if lable[i] = -1 then begin
                   lable[i] :=lable[u]+1;
                   inc(tail); q[tail]:=i;
                   if i = T then exit(true);
                end;
     inc(head);
     until head > tail;
     exit(false);
   end;


 procedure DFs;
   var
        top,u,i,r:        longint;
   begin
     top :=1; q[1] :=S;
     for i :=1 to NN do last[i] :=1;
     while top > 0 do begin
       u :=q[top];
       if u <> T then begin
          for i :=last[i] to NN do if (cost[u,i] >0) and (lable[i]=lable[u]+1)
                then break;
              last[u] :=i;
              if (cost[u,i] > 0) and (lable[i]=lable[u]+1)
                 then begin
                      inc(top); q[top] :=i;
                      end
                 else begin
                      lable[u] :=-1; dec(top);
                      end;
           end
       else begin
            r :=maxlongint;
            for i :=1 to top-1 do if cost[q[i],q[i+1]] <r then r :=cost[q[i],q[i+1]];
            inc(maxflow,r);
            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;
            i :=1;
            while cost[q[i],q[i+1]] > 0 do inc(i);
            top :=i;
            end;
       end;
   end;


 procedure Dinic;

   begin
     maxflow :=0;
     while BFS do DFS;
   end;

 procedure Main;
   var
         i,j:     longint;
         left:    array[1..maxn] of longint;

   begin
     for i :=1 to n do begin
         for j :=1 to n do left[j] :=a[i,j];
         for j :=1 to n do begin
             a[i,j] :=0; a[j,i] :=0;
             end;
         sumleft :=w[i]; for j :=1 to n do inc(sumleft,left[j]);
         if sumleft<maxwi then begin
            for j :=1 to n do begin
             a[i,j] :=left[j]; a[j,i] :=left[j];
             end;
            continue;
            end;
         fillchar(cost,sizeof(cost),0);
         make_graph;
         Dinic;
         if maxflow = totmatch - (sumleft-w[i])
            then begin
            inc(ans[0]); ans[ans[0]] :=i;
            end;
         for j :=1 to n do begin
             a[i,j] :=left[j]; a[j,i] :=left[j];
             end;
         end;
   end;

 procedure Print;
   var
        i:      longint;
   begin
     for i :=1 to ans[0]-1 do write(ans[i],' ');
     writeln(ans[ans[0]]);
   end;


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