记录编号	24940	评测结果	AAAAAAAAAA
题目名称	K- 联赛	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	0.650 s
提交时间	2011-05-25 19:08:11	内存使用	3.94 MiB

program kliansai;
var
  tt,win,i,j,n,z,t,p,q,k,s,ans:longint;
  w,dd,l:array[1..25]of longint;
  a:array[1..25,1..25]of longint;
  g:array[0..1000,1..1000]of longint;
  d:array[0..1000]of longint;
  bz:boolean;
function min(p,q:longint):longint;
begin
  if p<q then
    min:=p
  else
    min:=q
end;
procedure build;
begin
  fillchar(g,sizeof(g),0);
  tt:=0;
  z:=0;
  for p:=1 to n-1 do
    for q:=p+1 to n do
      if (a[p,q]>0)and(p<>i)and(q<>i) then
        tt:=tt+1;
  for p:=1 to n-1 do
    for q:=p+1 to n do
      if (a[p,q]>0)and(p<>i)and(q<>i) then
      begin  
        z:=z+1;
        g[0,z]:=a[p,q];
        g[z,tt+p]:=maxlongint;
        g[z,tt+q]:=maxlongint;
        g[tt+p,tt+n+1]:=win-w[p];
        g[tt+q,tt+n+1]:=win-w[q]
      end;
  z:=tt+n+1; 
end;
procedure bfs;
var
  r,ww:longint;
  team:array[1..10000]of longint;
  biaozhi:array[0..10000]of boolean;
begin
  t:=1;
  team[1]:=0;
  ww:=1;
  biaozhi[0]:=false;
  fillchar(d,sizeof(d),0);
  for r:=1 to z do
    biaozhi[r]:=true;
  while t<=ww do
  begin
    for r:=1 to z do
      if (g[team[t],r]>0)and(biaozhi[r]) then
      begin
        biaozhi[r]:=false;
        d[r]:=d[team[t]]+1;
        ww:=ww+1;
        team[ww]:=r;
      end;
    t:=t+1;
  end
end;
function dfs(u,flow:longint):longint;
var
  c,v,tmp:longint;
begin
    if u=z then  exit(flow);      
    c:=0; 		
    for v:=1 to z do 
    if (g[u,v]>0) and (d[v]=d[u]+1) then 
    begin
      tmp:=dfs(v,min(flow-c,g[u,v]));		 
      dec(g[u,v],tmp);
      inc(g[v,u],tmp);
      c:=c+tmp;
      if c=flow then 
        exit(c);
    end;
    if c=0 then
      d[u]:=maxlongint;
    exit(c)  
end;
begin
  assign (input,'kleague.in');
  reset (input);
  assign (output,'kleague.out');
  rewrite (output); 
    readln (n);
    for i:=1 to n do
      read (w[i],dd[i]);
    readln;
    for i:=1 to n do
    begin  
      for j:=1 to n do
      begin
        read (a[i,j]);
        s:=s+a[i,j];
        l[i]:=l[i]+a[i,j]
      end
    end;
    s:=s div 2;
    for i:=1 to n do
    begin
      k:=s-l[i];
      win:=w[i]+l[i];
      bz:=true;
      for j:=1 to n do
        if i<>j then
          if w[j]>win then
            bz:=false;
      if bz then
      begin
        build; 
        bfs;
        ans:=0;
        while d[z]<>0 do
        begin
          ans:=ans+dfs(0,maxlongint);
          bfs
        end;
        if ans=k then
          write (i,' ') 
      end
    end;
  close (input);
  close (output)
end.