首页 > 代码库 > poj3041-Asteroids , 二分图的最小顶点覆盖数 = 最大匹配数
poj3041-Asteroids , 二分图的最小顶点覆盖数 = 最大匹配数
点击打开链接
二分图的最小顶点覆盖数 = 二分图的最大匹配数
题意: 在N*N的网络中有K颗小行星。小行星i的位置是(Ri, Ci)。现在有一个强力的武器能够用一发光束将一整行或一整列的小行星消灭。想要利用这个武器消灭所有的小行星最少需要几发光束?
分析: 以小行星的左右坐标建立二分图,就可以看出是求二分图的最小顶点覆盖数。
#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 left[maxn];//left[i]为右边第i个点的匹配点编号,-1表示不存在 bool T[maxn];//T[i]为右边第i个点是否已标记 int right[maxn]; //求最小覆盖用 bool S[maxn]; //求最小覆盖用 void init(int n, int m){ this->n = n; this->m = m; for(int i=0; i<n; ++i) G[i].clear(); } void AddEdge(int u, int v){ G[u].push_back(v); } bool match(int u){ S[u] = true; for(int i=0; i<G[u].size(); ++i){ int v = G[u][i]; if(!T[v]){ T[v] = true; if(left[v]==-1 || match(left[v])){ left[v] = u; right[u] = v; return true; } } } return false; } //求最大匹配 int solve() { memset(left, -1, sizeof left ); memset(right, -1, sizeof right ); int ans = 0; for(int u=0; u<n; ++u){ //从左边结点u开始增广 memset(S, 0, sizeof S ); memset(T, 0, sizeof T ); if(match(u)) ans++; } return ans; } //求最小覆盖。 X 和 Y为最小覆盖中的点集 int mincover(vector<int>& X, vector<int>& Y){ int ans = solve(); memset(S, 0, sizeof S ); for(int u =0; u<n; ++u) if(right[u]==-1) match(u); //从所有X未盖点出发增广 for(int u=0; u<n; ++u) if(!S[u]) X.push_back(u); //X中的未标记点 for(int v=0; v<m; ++v) if(T[v]) Y.push_back(v); //Y中的已标记点 return ans; } }; BPM solver; int main() { int i, j, n, k; scanf("%d%d", &n, &k); solver.init(n, n); for(i=0; i<k; ++i) { int x, y; scanf("%d%d", &x, &y); x--; y--; solver.AddEdge(x, y); //有向图 } int ans = solver.solve(); printf("%d\n", ans); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。