爱华网刚开始用网络流做这道题目，可是限于水平没写出来。后来看了二分图，觉得这次才真的解出来了。很基础的二分图最大匹配，我用匈牙利算法写的。
【附匈牙利算法程序】Constdx:array[1..4]of -1..1=(1,0,-1,0);dy:array[1..4]of -1..1=(0,1,0,-1);VARmap:array[1..10000,1..10]oflongint;//注意用临接表，邻接矩阵会爆内存v,link:array[1..10000]oflongint;//v记录临接表与节点相连的点数，link记录二分图匹配时的点can:array[1..10000]ofboolean;//记录是否可以放棋子cover:array[1..10000]ofboolean;//计算最大匹配时的访问标志i,m,n,j,maxp :longint;Procedure init;//读入数据，把二维的数据转化成一维的（这个思想是Kudo神牛传授的...）vari,x,y,j,k,tmp,tmpx:longint;beginfillchar(can,sizeof(can),true);fillchar(v,sizeof(v),0);//初始化readln(n,m);for i:=1 to m do begin readln(x,y); can[(x-1)*n+y]:=false; end;for i:=1 to n do for j:=1 to n do begin if can[(i-1)*n+j]then begin tmp:=(i-1)*n+j;//当前(i,j)在二分图的位置标号 for k:=1 to 4 do//讨论上下左右四个相邻格子，建立相应的联系 if(i+dx[k]>0)and(j+dy[k]>0)and(i+dx[k]<=n)and(j+dy[k]<=n)and(can[(i+dx[k]-1)*n+j+dy[k]])then begin tmpx:=(i+dx[k]-1)*n+j+dy[k];//相邻的点在二分图的位置标号 inc(v[tmp]);map[tmp,v[tmp]]:=tmpx;//建立二分图 inc(v[tmpx]);map[tmpx,v[tmpx]]:=tmp; end; end; end;end;Function find(i:longint):boolean;//最大匹配varq,k,m:longint;beginfind:=true;for k:=1 to v[i] do begin m:=map[i,k]; if not cover[m] then beginq:=link[m];link[m]:=i;cover[m]:=true; if (q=0)or find(q) thenexit; link[m]:=q; end; end;exit(false);end;Procedure main;vari,j:longint;beginfor i:=1 to n*n do begin fillchar(cover,sizeof(cover),0); find(i); end;maxp:=0;for i:=1 to n*n do iflink[i]<>0 theninc(maxp);//求最大匹配end;Begininit;main;writeln(maxp div 2);End.
#01:Accepted(59ms, 1164KB)
#02:Accepted(28ms, 1136KB)
#03:Accepted(0ms, 1128KB)
#04:Accepted(0ms, 1120KB)
#05:Accepted(4ms, 1120KB)
#06:Accepted(0ms, 1120KB)
#07:Accepted(75ms, 1196KB)
![TYVJP1035[棋盘覆盖] 棋盘覆盖问题](http://img.aihuau.com/images/01111101/01121441t012bd7786c6f2a1dd2.gif)
#08:Accepted(90ms, 1188KB)
#09:Accepted(0ms, 1120KB)
#10:Accepted(0ms, 1120KB)
Accepted/ 100 /257ms / 1196KB
