?http://www.lydsy.com/JudgeOnline/problem.php?id=4808

題意：

?

?

思路：

這圖中的兩個馬只能選一個，二選一，很像二分圖吧，對能互吃的兩個棋子連線，在所選的任意兩個棋子中，都不能互相有連線，這不就是最大點獨立集嗎？

最大獨立集 = 頂點個數 - 最大匹配。記得把壞了的格子去掉。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 int n,m,tot; 7 int mp[205][205], head[40005], mark[40005]; 8 bool vis[40005]; 9 10 struct node 11 { 12 int v,next; 13 }e[8*40005]; 14 15 int dx[] = {-2,-2,-1,-1,1,1,2,2}; 16 int dy[] = {1,-1,2,-2,2,-2,1,-1}; 17 18 void addEdge(int u, int v) 19 { 20 e[tot].v = v; 21 e[tot].next = head[u]; 22 head[u] = tot++; 23 } 24 25 bool match(int u) 26 { 27 for(int i=head[u];i!=-1;i=e[i].next) 28 { 29 int v = e[i].v; 30 if(!vis[v]) 31 { 32 vis[v] = true; 33 if(mark[v]==-1 || match(mark[v])) 34 { 35 mark[v] = u; 36 return true; 37 } 38 } 39 } 40 return false; 41 } 42 43 int main() 44 { 45 //freopen("in.txt","r",stdin); 46 int num = 0; 47 scanf("%d%d",&n,&m); 48 for(int i=1;i<=n;i++) 49 for(int j=1;j<=m;j++) 50 { 51 scanf("%d",&mp[i][j]); 52 if(mp[i][j]) num++; 53 } 54 tot = 0; 55 memset(head,-1,sizeof(head)); 56 for(int i=1;i<=n;i++) 57 for(int j=1;j<=m;j++) 58 { 59 if(!mp[i][j]) 60 { 61 for(int k=0;k<8;k++) 62 { 63 int x = i+dx[k]; 64 int y = j+dy[k]; 65 if(x<1 || x>n || y<1 || y>m) continue; 66 if(mp[x][y]==1) continue; 67 int p1 = (i-1)*m+j; 68 int p2 = (x-1)*m+y; 69 addEdge(p1,p2); 70 } 71 } 72 } 73 int sum = 0; 74 memset(mark,-1,sizeof(mark)); 75 for(int i=1;i<=n*m;i++) 76 { 77 memset(vis,false,sizeof(vis)); 78 if(match(i)) sum++; 79 } 80 printf("%d\n",n*m-num-sum/2); 81 return 0; 82 }

?

轉載于:https://www.cnblogs.com/zyb993963526/p/7904002.html

總結

以上是生活随笔為你收集整理的BZOJ 4808: 马（二分图最大点独立集）的全部內容，希望文章能夠幫你解決所遇到的問題。

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