題目：Antenna Placement

?

題意：

一個矩形中，有N個城市’*’，現在這n個城市都要覆蓋無線，若放置一個基站，那么它至多可以覆蓋相鄰的兩個城市。

問至少放置多少個基站才能使得所有的城市都覆蓋無線？

看本題更詳細解法，請戳這里。

?

#include <iostream> #include <string.h>#define N 1150int linker[N]; bool used[N]; int map[N][N]; int g[N][N];int uN,vN;int dire_r[4]={-1,1,0,0}; int dire_c[4]={0,0,-1,1};bool DFS(int u) {int v;for(v=1;v<=vN;v++){if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||DFS(linker[v])){linker[v]=u;return true;}}}return false; }int Hungary() {int u;int ret=0;memset(linker,-1,sizeof(linker));for(u=1;u<=uN;u++){memset(used,false,sizeof(used));if(DFS(u)) ret++;}return ret; }int main() {char ch;int n,m,t;int i,j,k,p;std::cin>>t;while(t--){p=0;std::cin>>n>>m;memset(g,0,sizeof(g));memset(map,0,sizeof(map));for(i=1;i<=n;i++){for(j=1;j<=m;j++){std::cin>>ch;if(ch=='*')map[i][j]=++p;}}for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(map[i][j]){for(k=0;k<4;k++){int x=i+dire_r[k];int y=j+dire_c[k];if(map[x][y])g[map[i][j]][map[x][y]]=1;}}}}uN=vN=p;int ans=Hungary();std::cout<<uN-ans/2<<std::endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ3020深度解析(二分图--最小路径覆盖)的全部內容，希望文章能夠幫你解決所遇到的問題。

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