骑士共存问题

题意略过，把棋盘上点交叉黑白染色，坏点为-1，则每个骑士在合理跳跃的前提下总会跳到一个不同颜色的点，我们把这两个点连边，

问题转化为最大独立子集问题，用匈牙利最大数据0.39水过，第9个点用cena暴栈，但是直接运行没有问题，囧

View Code

  1 program knight(input,output);
  2 type
  3    node    = ^link;
  4    link    = record
  5          goal : longint;
  6          next : node;
  7       end;      
  8 var
  9    l      : array[0..41000] of node;
 10    map      : array[0..201,0..201] of integer;
 11    number : array[0..201,0..201] of longint;
 12    lk      : array[0..41000] of longint;
 13    v      : array[0..41000] of boolean;
 14    n,m      : longint;
 15 procedure init;
 16 var
 17    i,j     : longint;
 18    sum     : longint;
 19    xx,yy : longint;
 20 begin
 21    readln(n,m);
 22    for i:=1 to n*n do
 23       l[i]:=nil;
 24    map[1,1]:=0;
 25    for i:=2 to n do
 26       map[1,i]:=1-map[1,i-1];
 27    for i:=2 to n do
 28       for j:=1 to n do
 29      map[i,j]:=1-map[i-1,j];
 30    sum:=0;
 31    for i:=1 to n do
 32       for j:=1 to n do
 33       begin
 34      inc(sum);
 35      number[i,j]:=sum;
 36       end;
 37    for i:=1 to m do
 38    begin
 39       readln(xx,yy);
 40       map[xx,yy]:=-1;
 41    end;
 42 end; { init }
 43 procedure add(x1,y1,x2,y2 : longint );
 44 var
 45    tt : node;
 46 begin
 47    if (x1<1)or(x1>n)or(x2<1)or(x2>n) then
 48       exit;
 49    if (y1<1)or(y1>n)or(y2<1)or(y2>n) then
 50       exit;
 51    if (map[x1,y1]=-1)or(map[x2,y2]=-1) then
 52       exit;
 53    new(tt);
 54    tt^.goal:=number[x2,y2];
 55    tt^.next:=l[number[x1,y1]];
 56    l[number[x1,y1]]:=tt;
 57 end; { add }
 58 procedure make_graph();
 59 var
 60    i,j : longint;
 61 begin
 62    for i:=1 to n do
 63       for j:=1 to n do
 64      if map[i,j]=0 then
 65      begin
 66         add(i,j,i-2,j-1);
 67         add(i,j,i-1,j-2);
 68         add(i,j,i-2,j+1);
 69         add(i,j,i-1,j+2);
 70         add(i,j,i+1,j-2);
 71         add(i,j,i+1,j+2);
 72         add(i,j,i+2,j-1);
 73         add(i,j,i+2,j+1);
 74      end;
 75 end; { make_graph }
 76 function find(now :longint ):boolean;
 77 var
 78    t : node;
 79 begin
 80    t:=l[now];
 81    while t<>nil do
 82    begin
 83       if not v[t^.goal] then
 84       begin
 85      v[t^.goal]:=true;
 86      if (lk[t^.goal]=0)or(find(lk[t^.goal])) then
 87      begin
 88         lk[t^.goal]:=now;
 89         exit(true);
 90      end;
 91       end;
 92       t:=t^.next;
 93    end;
 94    exit(false);
 95 end; { find }
 96 procedure main;
 97 var
 98    i,j      : longint;
 99    answer : longint;
100 begin
101    answer:=0;
102    for i:=1 to n do
103       for j:=1 to n do
104      if map[i,j]=0 then
105      begin
106         fillchar(v,sizeof(v),false);
107         if find(number[i,j]) then
108            inc(answer);
109      end;
110    writeln(n*n-m-answer);
111 end; { main }
112 begin
113    assign(input,'knight.in');reset(input);
114    assign(output,'knight.out');rewrite(output);
115    init;
116    make_graph;
117    main;
118    close(input);
119    close(output);
120 end.