lp3355 网络流24题-骑士共存问题

首先我们观察这道题。
暴力地状压DP或者之类的操作显然会MLE/TLE。
我们发现，横坐标和纵坐标相加的和的奇偶性相同的格子永远不可能互相攻击到。
故而我们考虑建一张二分图。将横纵坐标的和的奇偶性不同的格子分别放在左右边，然后在能相互攻击到的点之间连边。依据题意，不能相互攻击到，所以答案即是这张图的最大独立集。

二分图最大独立集应当如何求得？我们有一个定理：一张二分图的最大独立集的大小等同于顶点数它的最大匹配的数量。
我们考虑感性地证明这个定理。
很容易可以发现，两个点不能被同时选取，当且仅当它们之间有连边。
又因为，有连边的两个点必然是属于二分图的两端的。
故而，如果有两个点不能被同时选取，它们必然可以构成一个匹配。
对于二分图上的最大匹配，所有没有被匹配的点都可以被选取。这非常的显然，因为没有被匹配到的点之间必然没有连边。如果有连边，那么就可以增加匹配，与最大匹配矛盾。
而，对于每一个匹配，都可以选取一组匹配中的一个点。这是因为，对于一些连通的匹配，它们有且仅有一个部分（左边或者右边）会和未匹配点连接。
这也是很显然的，因为如果不是这样的话，就存在一条新的增广路径，就可以得到更多的匹配了。
注意：坐标如何哈希成一个数字。

#include<iostream>
#include<cstdio>

const int dx[8]={-2,-1,1,2,-2,-1,1,2};
const int dy[8]={1,2,2,1,-1,-2,-2,-1}; 

struct ee{
	int v;
	int nxt;
}e[160005];
int h[40005],et=0;

inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et; 
}

bool vis[40005],mp[205][205];
int n=0,m=0,usd[40005];

inline int calc(int X,int Y){
	return (X-1)*n+Y;
//	注意坐标哈希成数字的方式。 
}

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			vis[e[i].v]=1;
			if(!usd[e[i].v]||dfs(usd[e[i].v])){
				usd[e[i].v]=X;
				return 1;
			}
		}
	}
	return 0;
}
int st[40005],tp=0;
char out[205][205];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			mp[i][j]=0;
			usd[calc(i,j)]=0;
			out[i][j]='O';
		}
	}
	int x,y;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
//			printf("[%d %d] ",i,j);
			if(mp[i][j]||((i+j)&1)){
//				注意不是每次跳2而是判奇偶性。 
				continue;
			}
			st[++tp]=calc(i,j);
			out[i][j]='@'; 
			//注意有障碍的不仅是结束点，还有出发点。 
			for(int k=0;k<8;++k){
				x=i+dx[k],y=j+dy[k];
				if(x<=0||y<=0||x>n||y>n||mp[x][y]){
					continue;
				}
				out[x][y]='X';
				add(calc(i,j),calc(x,y));
			}
		}
	}
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=n;++j){
//			putchar(out[i][j]);
//		}
//		puts("");
//	}
	int ans=n*n-m;
//	减去被挖掉的点 
	for(int i=1;i<=tp;++i){
		for(int j=1;j<=n*n;++j){
			vis[j]=0;
		}
		ans-=dfs(st[i]);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}