首页 > 代码库 > POJ 3020 Antenna Placement ,二分图的最小路径覆盖
POJ 3020 Antenna Placement ,二分图的最小路径覆盖
题目大意:
一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。
问至少放置多少个基站才能使得所有的城市都覆盖无线?
无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2
路径覆盖就是在图中找一些路径,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联;
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn = 500 + 5; struct BPM { int n, m; vector<int> G[maxn]; int link[maxn]; bool vis[maxn]; void init(int n) { for(int i=0; i<=n+10; ++i) G[i].clear(); } void AddEdge(int u, int v) { G[u].push_back(v); } bool match(int u) { for(int i=0; i<G[u].size(); ++i) { int v = G[u][i]; if(!vis[v]) { vis[v] = true; if(link[v]==-1 || match(link[v])) { link[v] = u; return true; } } } return false; } int solve(int n) { this->n = n; memset(link, -1, sizeof link ); int ans = 0; for(int u=1; u<=n; ++u) { memset(vis, 0, sizeof vis ); if(match(u)) ans++; } return ans; } }; BPM solver; int mtx[maxn][maxn]; int dir[4][2]={{-1,0}, {1,0}, {0,1}, {0,-1} }; int main() { int t, h, w; scanf("%d", &t); while(t--) { scanf("%d%d", &h, &w); solver.init(h*w); memset(mtx, 0, sizeof mtx ); int i, j; char str[maxn]; int cnt = 0; for(i=1; i<=h; ++i) { scanf("%s", str); for(j=0; j<w; ++j) { if(str[j]=='*') mtx[i][j+1] = ++cnt; } } for(i=1; i<=h; ++i) for(j=1; j<=w; ++j) if(mtx[i][j]) for(int k=0; k<4; ++k) { int xx = i + dir[k][0]; int yy = j + dir[k][1]; if(mtx[xx][yy]) solver.AddEdge(mtx[i][j], mtx[xx][yy]); } int ans = solver.solve(cnt); printf("%d\n", cnt - ans/2); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。