題目鏈接：點擊查看

題目大意：給出一個n*m的矩陣，每個點都有一個權值，-1表示該格子為警衛，否則表示該格子有寶物：

當前點的權值二進制為1的地方代表需要一個警衛（編號為二進制從右往左數的位置），警衛的位置如下圖所示：

現在已知寶物的信息后，我們需要將寶物替換成警衛來保護剩余的寶物，問最少可以更換幾個寶物為警衛，另外空格子不能進行操作，即不能在空格子上添加警衛，也不能將寶物移除而不增加警衛，只能用警衛替換掉寶物

題目分析：這個題一開始真的是一點思路也沒有的，看了網上的題解后真得驚到了，二分圖竟然還能這樣劃分子集。。直接說一下吧，對于這個題目來說，每一個寶物和警衛的坐標，奇偶性都是不同的，也就是(x+y)的奇偶性，這樣一來我們就可以將所有寶物以及警衛的位置，分為奇數和偶數兩個子集，然后建邊，因為二分圖一般來說都是有向圖，我們可以選擇讓奇數的坐標指向偶數的坐標，或者讓偶數的坐標指向奇數的坐標，只要上下統一起來就可以，因為題目的要求是每個寶物都需要一定數量警衛來看守，換句話說每一個點都必須占用，這樣題目就轉換為了求最小點覆蓋的問題，也就是求出最小數量的點，讓所有的邊都被覆蓋，也就等價于二分圖的最大匹配問題了

這里還有一個問題，因為矩陣最大給的是50*50，奇偶劃分之后，如果用鄰接矩陣建邊然后n*n枚舉的話，時間復雜度是50*50*50*50，再加上是多組輸入，所以時間復雜度肯定是頂不住的，這樣我們就只能用鄰接表來存邊了，懶得寫鏈式前向星，就寫個鄰接表湊活著用吧。。

代碼：

#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=55;const int b[12][2]={-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,0,0,1,1,0,0,-1};//警衛坐標，按照序號枚舉int n,m;vector<int>node[N*N];int a[N][N];int match[N*N];bool vis[N*N];int num[N][N];int cnt1,cnt2;//cnt1:記錄奇坐標的編號 cnt2:記錄偶坐標的編號bool dfs(int x) {for(auto i:node[x]){if(!vis[i]){vis[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}}return false; }void init() {memset(match,0,sizeof(match));for(int i=1;i<=n*m;i++)node[i].clear();cnt1=cnt2=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int kase=0;while(scanf("%d%d",&n,&m)!=EOF&&n+m){init();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if((i+j)&1)num[i][j]=++cnt1;elsenum[i][j]=++cnt2;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i][j]==-1)continue;for(int k=0;k<12;k++){if(!(a[i][j]&(1<<k)))continue;int x=i+b[k][0];int y=j+b[k][1];if(x<=0||y<=0||x>n||y>m)continue;if(a[x][y]==-1)continue;if((i+j)&1)//這里我規定奇坐標指向偶坐標node[num[i][j]].push_back(num[x][y]);elsenode[num[x][y]].push_back(num[i][j]);}}int ans=0;for(int i=1;i<=cnt1;i++)//跑一遍奇坐標{memset(vis,false,sizeof(vis));if(dfs(i))ans++;}printf("%d. %d\n",++kase,ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 3360 National Treasures(最小点覆盖-二分图最大匹配+奇偶拆点)的全部內容，希望文章能夠幫你解決所遇到的問題。

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