SSL 1344 Knights#匈牙利算法#

题目

求在一个棋盘上放置尽可能多的马，并使他们不互相攻击。

分析

可以把这个转化成二分图，求最大独立集。
最大独立集=点的数量-最大匹配。
用匈牙利算法，求出最大匹配就可以了。
当然构图是很费时间的。

在1的位置互不影响，所以可以这样划分，建立二分图。

代码（邻接表，$6192ms$）

#include 
#include 
#include 
using namespace std;
struct node{int y,next;}e[160001]; 
int n,m1,m2,ls[20001],link[20001],m,ans; 
bool cover[20001]; short v[201][201];
const int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
bool find(int x){int t=ls[x];while (t){if (!cover[e[t].y]){cover[e[t].y]=1;int q=link[e[t].y];link[e[t].y]=x;if (!q||find(q)) return 1;link[e[t].y]=q;}t=e[t].next;}return 0;
}
void add(int x,int y){e[++m].y=y;e[m].next=ls[x]; ls[x]=m;}
int main(){n=in(); m=in(); ans=n*n-m;while (m--) v[in()][in()]=-1;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (!v[i][j]&&(i+j)%2==0){v[i][j]=++m1;for (int k=0;k<8;k++){int x=i+dx[k],y=j+dy[k];if (x<1||y<1||x>n||y>n) continue;if (!v[x][y]) v[x][y]=++m2;if (v[x][y]!=-1) add(m1,v[x][y]);//建图}}for (int i=1;i<=m1;i++) memset(cover,0,sizeof(cover)),ans-=find(i);printf("%d",ans);return 0;
}

代码（$邻接矩阵,311ms$）

#include 
#include 
#include 
using namespace std;
unsigned short v[201][201],n,m,m1,m2,ans,x[20001],y[20001],link[20001]; bool cover[20001];
const int dx[8]={1,1,-1,-1,2,2,-2,-2},dy[8]={2,-2,2,-2,1,-1,1,-1};
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
bool find(int num){int x1=x[num],y1=y[num];for (int i=0;i<8;i++){int x2=x1+dx[i],y2=y1+dy[i]; int j=v[x2][y2];if (x2<1||y2<1||x2>n||y2>n||j==5e4||cover[j]) continue;int q=link[j]; link[j]=num; cover[j]=1;if (!q||find(q)) return 1; link[j]=q; }return 0;
}
int main(){n=in(); m1=in(); ans=n*n-m1;while (m1--) v[in()][in()]=5e4; m1=0;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (v[i][j]!=5e4){if ((i+j)%2==0) v[i][j]=++m2;else v[i][j]=++m1,x[m1]=i,y[m1]=j;}for (int i=1;i<=m1;i++) memset(cover,0,sizeof(cover)),ans-=find(i);printf("%d",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！