題目鏈接：點擊查看

題目大意：給出一個n*m的棋盤，有t個點是禁止放棋子的，現在按照馬走日的規則，問在互不影響的情況下最多能放多少個馬

題目分析：這里首先簡單介紹一下二分圖最大獨立集的定義：

通俗來講，圖的獨立集就是“任意兩點之間都沒有邊相連”的點集。包含點數最多的一個就是圖的最大獨立集

公式：

頂點數-最大匹配數

這樣一來，因為馬走日的規則也滿足奇偶拆點的規則，所以在這個題目中我們可以奇偶建邊，然后按照公式計算就好了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;const int b[8][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};int can[N][N];int num1[N][N],num2[N][N],cnt1,cnt2;vector<int>node[N*N];int match[N*N];bool vis[N*N];bool dfs(int x) {for(auto y:node[x]){if(!vis[y]){vis[y]=true;if(!match[y]||dfs(match[y])){match[y]=x;return true;}}}return false; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m,t;scanf("%d%d%d",&n,&m,&t);for(int i=1;i<=t;i++){int x,y;scanf("%d%d",&x,&y);can[x][y]=true;}for(int i=1;i<=n;i++)//奇偶拆點for(int j=1;j<=m;j++){if(can[i][j])continue; if((i+j)&1)num1[i][j]=++cnt1;elsenum2[i][j]=++cnt2;}for(int i=1;i<=n;i++)//建邊for(int j=1;j<=m;j++){if(can[i][j])continue;for(int k=0;k<8;k++){int xx=i+b[k][0];int yy=j+b[k][1];if(xx<=0||yy<=0||xx>n||yy>m)continue;if(can[xx][yy])continue;if((i+j)&1)node[num1[i][j]].push_back(num2[xx][yy]);elsenode[num1[xx][yy]].push_back(num2[i][j]);}}int ans=n*m-t;//注意這里，頂點數是n*m-t，一開始傻傻的設置成n，wa了好幾發for(int i=1;i<=cnt1;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans--;}printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CH - 6901 骑士放置(二分图最大独立集-二分图最大匹配+奇偶拆点)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。