題意：

N行M列的矩陣，每個格子里不是 * 就是 O 。

* ：是一個利益點。

O：是一個空白點。

每次可以用一個圈覆蓋相鄰的兩個*。（左右相鄰或上下相鄰）。

問最少需要多少個圈可以覆蓋所有的*。

?

思路：

把每個格子變成一個數，總共有N*M個數。構造二分圖，左右的數字都分別是1....N*M。

若兩個*可以被一個圈覆蓋，則將它們對應在左邊、右邊的點連上線。

答案即為：*的總數 - 最大二分匹配的值/2（因為有一半是對稱的）。

?

代碼：

int T,n,m; vector<int> graph[405]; bool bmask[405]; int cx[405],cy[405]; char s[45][15];int findPath(int u){int L=graph[u].size();rep(i,0,L-1){int v=graph[u][i];if(!bmask[v]){bmask[v]=true;if(cy[v]==-1||findPath(cy[v])){cy[v]=u;cx[u]=v;return 1;}}}return 0; } int MaxMatch(){int ans=0;rep(i,1,n*m) cx[i]=cy[i]=-1;rep(i,1,n*m) if(cx[i]==-1){mem(bmask,false);ans+=findPath(i);}return ans; }int main(){cin>>T;while(T--){scanf("%d%d",&n,&m);rep(i,1,n*m) graph[i].clear();int cc=0;rep(i,1,n) scanf("%s",s[i]);rep(i,1,n){rep(j,0,m-1) if(s[i][j]=='*'){int num=m*(i-1)+j+1;int u=i, v=j+1;if(v-1>=1 && s[u][j-1]=='*') graph[num].push_back(num-1);if(v+1<=m && s[u][j+1]=='*') graph[num].push_back(num+1);if(u-1>=1 && s[u-1][j]=='*') graph[num].push_back(num-m);if(u+1<=n && s[u+1][j]=='*') graph[num].push_back(num+m);++cc;}}int dd=MaxMatch();printf("%d\n",cc-dd/2);} }

?

轉載于:https://www.cnblogs.com/fish7/p/4088519.html

總結

以上是生活随笔為你收集整理的poj 3020 Antenna Placement（二分图最大匹配）的全部內容，希望文章能夠幫你解決所遇到的問題。

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