题目链接：骑士共存问题
贴一个很相似的题吧：方格取数
这两个题：如果放在了一起，相信应该都会有思路的吧！
黑白染色法：求得最小割，然后用所有的可行点减去最小割就是：最大独立集
然后呢，建图有两种方法的
第一种方法：不拆点：那么我们需要对每个节点黑白染色：注意！
这个染色与方格取数不一样了：因为有些点是障碍，那么黑白点的染色方案就变了
在计算的时候，只有非障碍点才编号
然后在连边的时候
源点S向所有的（i+j）%2==1的连边
所有的（i+j）%2==0向汇点T连边
然后，按照骑士的规则
枚举所有的可能情况就好
int main(){
//freopen("input.txt","r",stdin);
int m,x,y,c;
while(scanf("%d%d",&n,&m)!=EOF){
memset(mp,0,sizeof(mp));
c=s=0;t=n*n+1;tot=t+1;
init();
//for(int i=1;i<=n;i++)
// for(int j=1;j<=n;j++)
// printf("%d%c",mp[i][j],j==n?'\n':' ');
int ans=n*n-m;
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++)
if (mp[i][j]!=-1)
mp[i][j]=++c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if (mp[i][j]!=-1){
//(i*j)&1==1
//i和j都是奇数
//!(i&1)说明i是偶数
//!(j&1)说明j是偶数
//if((i*j)&1 || ((!(i&1))&&(!(j&1)))){
if ((i+j)%2==0){
addedge(s,mp[i][j],1);
for(int k=0;k<8;k++){
int nx=i+dx[k];
int ny=j+dy[k];
if (nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]!=-1)
addedge(mp[i][j],mp[nx][ny],1);
}
}
else addedge(mp[i][j],t,1);
}
}
int mflow;
//mflow=dinic(s,t,tot);
mflow=sap(s,t,tot);
//printf("%d\n",mflow);
printf("%d\n",ans-mflow);
}
return 0;
}
方法2：拆点
拆点就不需要考虑这么多了
把X集合和Y集合全部分开想
但是求出的最小割是原来的2倍
因为每条边都有两条啦，可以画画图就懂细节了
#include<bits/stdc++.h>
using namespace std;
const int maxn=105000;
const int maxm=1000050;
const int maxl=250;
const int INF=0x3f3f3f3f;
int s,t,tot,n;
int mp[maxl][maxl];
int dx[]={2,2,1,1,-1,-1,-2,-2};
int dy[]={1,-1,2,-2,2,-2,1,-1};
struct Edge{
int to,nxt,cap,flow;
}edge[maxm];
int tol,Head[maxn];
void init(){
memset(Head,-1,sizeof(Head));
tol=0;
}
void addedge(int u,int v,int w,int rw=0){
edge[tol].to=v;
edge[tol].cap=w;
edge[tol].flow=0;
edge[tol].nxt=Head[u];
Head[u]=tol++;
edge[tol].to=u;
edge[tol].cap=rw;
edge[tol].flow=0;
edge[tol].nxt=Head[v];
Head[v]=tol++;
}
int Q[maxn],dep[maxn],cur[maxn],pre[maxn];
int gap[maxn];
void BFS(int Start,int End){
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]=1;
int Front=0,Rear=0;
dep[End]=0;
Q[Rear++]=End;
while(Front!=Rear){
int u=Q[Front++];
for(int i=Head[u];i!=-1;i=edge[i].nxt){
int v=edge[i].to;
if (dep[v]!=-1) continue;
Q[Rear++]=v;
dep[v]=dep[u]+1;
gap[dep[v]]++;
}
}
}
int S[maxn];
int sap(int Start,int End,int N){
BFS(Start,End);
memcpy(cur,Head,sizeof(Head));
int top=0;
int u=Start;
int ans=0;
while(dep[Start]<N){
if (u==End){
int Min=INF;
int inser;
for(int i=0;i<top;i++)
if (Min>edge[S[i]].cap-edge[S[i]].flow){
Min=edge[S[i]].cap-edge[S[i]].flow;
inser=i;
}
for(int i=0;i<top;i++){
edge[S[i]].flow+=Min;
edge[S[i]^1].flow-=Min;
}
ans+=Min;
top=inser;
u=edge[S[top]^1].to;
continue;
}
bool flag=false;
int v;
for(int i=cur[u];i!=-1;i=edge[i].nxt){
v=edge[i].to;
if (edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){
flag=true;
cur[u]=i;
break;
}
}
if (flag){
S[top++]=cur[u];
u=v;
continue;
}
int Min=N;
for(int i=Head[u];i!=-1;i=edge[i].nxt)
if (edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){
Min=dep[edge[i].to];
cur[u]=i;
}
gap[dep[u]]--;
if (!gap[dep[u]]) return ans;
dep[u]=Min+1;
gap[dep[u]]++;
if (u!=Start) u=edge[S[--top]^1].to;
}
return ans;
}
/*
int sap(int Start,int End,int N){
memset(gap,0,sizeof(gap));
memset(dep,0,sizeof(dep));
memcpy(cur,Head,sizeof(Head));
int u=Start;
pre[u]=-1;
gap[0]=N;
int ans=0;
while(dep[Start]<N){
if (u==End){
int Min=INF;
for(int i=pre[u];i!=-1;i=pre[edge[i^1].to])
if (Min>edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
for(int i=pre[u];i!=-1;i=pre[edge[i^1].to]){
edge[i].flow+=Min;
edge[i^1].flow-=Min;
}
u=Start;
ans+=Min;
continue;
}
bool flag=false;
int v;
for(int i=cur[u];i!=-1;i=edge[i].nxt){
v=edge[i].to;
if (edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){
flag=true;
cur[u]=pre[v]=i;
break;
}
}
if (flag){
u=v;
continue;
}
int Min=N;
for(int i=Head[u];i!=-1;i=edge[i].nxt)
if (edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){
Min=dep[edge[i].to];
cur[u]=i;
}
gap[dep[u]]--;
if (!gap[dep[u]]) return ans;
dep[u]=Min+1;
gap[dep[u]]++;
if (u!=Start) u=edge[pre[u]^1].to;
}
return ans;
}
*/
int getpoint(int x,int y){
return (x-1)*n+y;
}
int main(){
//freopen("input.txt","r",stdin);
int m,x,y;
while(scanf("%d%d",&n,&m)!=EOF){
memset(mp,0,sizeof(mp));
s=0;t=2*n*n+1;tot=t+1;
init();
int ans=n*n-m;
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++){
if (!mp[i][j]){
addedge(s,getpoint(i,j),1);
addedge(getpoint(i,j)+n*n,t,1);
}
for(int k=0;k<8;k++){
int nx=i+dx[k];
int ny=j+dy[k];
if (nx>=1&&nx<=n&&ny>=1&&ny<=n&&!mp[nx][ny])
addedge(getpoint(i,j),getpoint(nx,ny)+n*n,1);
}
}
int mflow;
//mflow=dinic(s,t,tot);
mflow=sap(s,t,tot);
printf("%d\n",ans-mflow/2);
}
return 0;
}
这个题最坑的是细节！
n=200，在第一种方法里，建图中的点可能有200*200=40000个点
而拆点之后则是80000个啊
初始化的数据大小一定要经过计算的！
京公网安备 11010502036488号