UVA 11419SAM I AM(输出 最小覆盖点 )

参考博客:如何找取 最小覆盖点集合

题意:R*C大小的网格,网格上面放了一些目标。可以再网格外发射子弹,子弹会沿着垂直或者水平方向飞行,并且打掉飞行路径上的所有目标,计算最小多少子弹,各从哪些位置发射,才能将所有的目标全部打掉

分析:就是求最小覆盖点 以及 输出所有的覆盖点

最小覆盖点 == 最大匹配数

个人理解:

最大匹配数是用匈牙利算法求的,就是从左边一个点开始找到他看上的那个妹纸,如果那个妹纸已经名花有有主就跟那个男生换一个...沿着 ( 没匹配 - 匹配边 -... - 没匹配边)  这样的增广路径来探寻。

假设已经求得最大匹配,怎么证明最大匹配等于最小覆盖点呢, 首先从左边没有匹配上的边开始 找增光路,找到所有的点都标记一下,当然不会找到一个全的,如果全的话就不是最大匹配,又多出来一个匹配边。  那么最小覆盖点就是 左边 没标记 + 右边标记的, 为什么呢? 对于左边没标记的 也就是说他有 匹配边 同时与他相连的右边那个点 没被标记,(如果右边标记, 他就被标记了),所有左边 所有没标记的点 是 最大匹配边的一部分 , 然后右边标记的呢,从左边没标记点开始连向右边的点,右边的这个点一定被匹配上了的,右边标记的点也是匹配边的一个端点,组成了 最大匹配边的那一部分,  说白点就是 左边没标记的匹配边 就是这两个点就是相互喜欢型的,而右边标记的就是有别人暗恋的。

 #include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int Max = + ;
int n, m;
vector<int> G[Max];
int Left[Max], Right[Max]; // left[i]表示右边的i对应左边的编号,right[i]表示左边的i对应右边的编号
bool vis[Max]; // 右边的点有没有访问
bool S[Max]; // 左边的点有没有没标记
void init()
{
for (int i = ; i < n; i++)
G[i].clear();
}
void addedge(int u, int v)
{
G[u].push_back(v);
}
bool mach(int u)
{
S[u] = true;
int len = (int) G[u].size();
for (int i = ; i < len; i++)
{
int v = G[u][i];
if (!vis[v])
{
vis[v] = true;
if (Left[v] == - || mach(Left[v]))
{
Left[v] = u; // 存储匹配关系
Right[u] = v;
return true;
}
}
}
return false;
}
int solve()
{
memset(Left, -, sizeof(Left));
memset(Right, -, sizeof(Right));
int ans = ;
for (int i = ; i < n; i++)
{
memset(vis, , sizeof(vis));
if (mach(i))
ans++;
}
return ans;
}
int mincover(vector<int> & X, vector<int> & Y)
{
int ans = solve();
memset(vis, , sizeof(vis));
memset(S, , sizeof(S));
for (int i = ; i < n; i++)
{
if (Right[i] == -) // 从左边没有匹配的点开始找增广路
mach(i);
}
for (int i = ; i < n; i++)
if (!S[i]) // 左边没标记
X.push_back(i);
for (int i = ; i < m; i++)
if (vis[i]) // 右边标记的
Y.push_back(i);
return ans;
}
int main()
{
int c, r, N;
while (scanf("%d%d%d", &n, &m, & N) != EOF)
{
if (n == && m == && N == )
break;
init();
for (int i = ; i < N; i++)
{
scanf("%d%d", &r, &c);
r--;
c--;
addedge(r, c);
}
vector<int> X, Y;
int ans = mincover(X, Y);
printf("%d", ans);
for (int i = ; i < (int) X.size(); i++)
printf(" r%d", X[i] + );
for (int j = ; j < (int) Y.size(); j++)
printf(" c%d", Y[j] + );
printf("\n");
} return ;
}
上一篇:浅谈移动应用的跨平台开发工具(Xamarin和React Native)


下一篇:GCD常用方法