题意：在n*m的网格上填马，其攻击范围是±3，±1这种类型，每个格子有个权值，有些格子可以选，有些不能选，求一种字典序最小的，马互不攻击的，权值之和最大的一种方案
明显按行奇偶染色，就变成了二分图上的最大权独立集的问题，这个是个经典模型，然后考虑怎么输方案，按字典序枚举每个位置，如果想让这个位置必须选，那么就是它连向源或汇的边变为oo，使得最小割割不开，则判断其合法性就是看有没有一条到汇（源）点的增广路，也就是一次bfs就可以了，因此判断复杂度也是o((n*m)^2)的。比赛的时候还是黄哥机智的提出了这个idea，否则我就得每次暴力流一遍了。
其实这题烦的不是算法，而是各种情况，譬如至少放一个马，或者是有负数，同时你又必须选它之类的，比赛时写了一遍，之后又re了一遍，改到拍不出错之后，又手构了几种情况才终于过了。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
const int dx[8]={-1,-3,-3,-1,1,3,3,1};
const int dy[8]={-3,-1,1,3,3,1,-1,-3};
const int oo=1073741819;
using namespace std;
int tail[20000],next[500000],sora[500000];
int flow[1050][1050],col[1050][1050],id[1050][1050],g[2][1050],d[1050],st[1050],w[1050][1050];
int s,t,n,m,ss,tot;
void origin()
{
s=n*m+1,t=s+1,ss=t;
for (int i=1;i<=t;i++) tail[i]=i,next[i]=0;
}
void link(int x,int y,int z)
{
++ss,next[tail[x]]=ss,tail[x]=ss,sora[ss]=y,next[ss]=0;
++ss,next[tail[y]]=ss,tail[y]=ss,sora[ss]=x,next[ss]=0;
flow[x][y]=z,flow[y][x]=0;
}
void doit(int x,int y)
{
for (int i=0;i<=7;i++) {
int nx=x+dx[i],ny=y+dy[i];
if (nx<1 || nx>n || ny<1 || ny>m || col[nx][ny]==2) continue;
link(id[x][y],id[nx][ny],oo);
}
}
bool bfs(int s,int t)
{
int h,r,ne,na;
for (int i=1;i<=t;i++) d[i]=oo;
h=r=0;
st[r=1]=s,d[s]=0;
for (;h<r;) {
ne=st[++h];
for (int i=ne;next[i];) {
i=next[i],na=sora[i];
if (flow[ne][na] && d[ne]+1<d[na]) {
d[na]=d[ne]+1;
st[++r]=na;
}
}
}
return d[t]<oo;
}
int dfs(int x,int low)
{
if (x==t) return low;
int sum=0,ne,tmp;
for (int i=x;next[i];) {
i=next[i],ne=sora[i];
if (flow[x][ne] && d[x]+1==d[ne]) {
if (flow[x][ne]<low) tmp=dfs(ne,flow[x][ne]);
else tmp=dfs(ne,low);
if (!tmp) d[ne]=oo;
flow[x][ne]-=tmp,flow[ne][x]+=tmp,sum+=tmp,low-=tmp;
if (!low) break;
}
}
return sum;
}
void bfs2(int s)
{
int h,r,ne,na;
for (int i=1;i<=t;i++) d[i]=oo;
h=r=0;
st[r=1]=s,d[s]=0;
for (;h<r;) {
ne=st[++h];
for (int i=ne;next[i];) {
i=next[i],na=sora[i];
if (flow[na][ne] && d[ne]+1<d[na]) {
d[na]=d[ne]+1;
st[++r]=na;
}
}
}
}
int T;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&T);
for (int test=1;T;T--,test++) {
printf("Case %d: ",test);
scanf("%d%d",&n,&m);
origin();
for (int i=1,s1=1;i<=n;i++)
for (int j=1;j<=m;j++,s1++)
scanf("%d",&w[i][j]),col[i][j]=0,id[i][j]=s1;
int p,q;
scanf("%d",&p);
for (int i=1;i<=p;i++) {
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
col[x][y]=1;
}
scanf("%d",&q);
for (int i=1;i<=q;i++) {
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
col[x][y]=2;
}
int M,M1,M2;
tot=0,M=-oo,M1=0,M2=0;
bool flag=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (col[i][j]!=2) {
if (col[i][j]==1 || w[i][j]>0) tot+=w[i][j],flag=1;
if (w[i][j]>M) M=w[i][j],M1=i,M2=j;
}
if (!flag && M<0) {
printf("%d\n",M);
printf("%d %d\n",M1-1,M2-1);
continue;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (col[i][j]!=2) {
if (i&1) {
if (col[i][j]==1) link(s,id[i][j],oo),doit(i,j);
else if (w[i][j]>=0) link(s,id[i][j],w[i][j]),doit(i,j);;
}
else {
if (col[i][j]==1) link(id[i][j],t,oo);
else if (w[i][j]>=0) link(id[i][j],t,w[i][j]);
}
}
int sum=0;
for (;bfs(s,t);sum+=dfs(s,oo)) ;
printf("%d\n",tot-sum);
for (int i=1;i<=s-1;i++) g[0][i]=d[i];
bfs2(t);
for (int i=1;i<=s-1;i++) g[1][i]=d[i];
int k=0,fl=0,lf=0;
//cout<<flow[id[5][2]][id[2][1]]<<' '<<flow[s][id[5][2]]<<endl;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (col[i][j]!=2 && (k!=tot-sum || fl!=p || !lf)) {
if (col[i][j]==1) {
printf("%d %d\n",i-1,j-1);
k+=w[i][j],fl++,lf++;
continue;
}
if (w[i][j]<0) continue;
//cout<<i<<'-'<<j<<endl;
if (i&1) {
if (g[1][id[i][j]]<oo) continue;
else {
printf("%d %d\n",i-1,j-1);
k+=w[i][j],lf++;
flow[s][id[i][j]]=oo;
bfs(s,t);
for (int i=1;i<=s-1;i++) g[0][i]=d[i];
}
}
else {
if (g[0][id[i][j]]<oo) continue;
else {
printf("%d %d\n",i-1,j-1);
k+=w[i][j],lf++;
flow[id[i][j]][t]=oo;
bfs2(t);
for (int i=1;i<=s-1;i++) g[1][i]=d[i];
}
}
}
}
return 0;
}