题目链接：https://vjudge.net/problem/UVA-11419
题解：
1.二分图匹配之最小点覆盖.：把x坐标和y坐标看成是点， 图中的目标看成是边，所以最终的目的是求出用最少的点，去覆盖掉所有的边。如果在M[x][y]处有目标，则连一条边x-y。接着跑一遍匈牙利算法。
2.除此之外，题目还要求输出最小覆盖点集。可知我们已经求出了最大匹配数，首先我们把所有的覆盖点都落在左边的匹配点上。但是这样做却不能保证所有的边都会被覆盖，因为假设左边有未匹配点，且这些未匹配点与右边的点（是匹配点但不是覆盖点）有边，那么这些边就没有被覆盖了。所以为了覆盖掉所有的边，我们需要把左边的覆盖点转移到右边的点上。
3.可知：从左边的未匹配点开始试找增广路，最终是找不到增广路的，否则最大匹配数就会+1了。所以我们可以得出一个结论：从左边的未匹配点开始遍历（访问过的点就不用再访问了），得到的路径为一棵树，且：路径上的首边必为未匹配边，尾边必为匹配边，且两种边交替出现，且最后一个点必为左边的匹配点（也是我们初始设置的覆盖点）。
4.上个结论有什么用呢？我们可以知道，最后一个覆盖点出现在末端，显然浪费了。所以为了充分利用覆盖点，我们得把覆盖点都放置在里面，且交替出现。所以，我们可以：从左边的未匹配点开始遍历。左边未访问到的点设为覆盖点， 右边访问到的点为覆盖点。
5.由于个人理解得不太到位，且语言表达一团糟，所以也解释得很糟糕。所以呈上一副最简单的图，方便理解：
其中点5 7 9就为初始设定的最小覆盖点集， 4 6 9为最终的覆盖点集。
对匈牙利算法的一些浅薄的认识：
枚举左边的每一个点，以此为出发点，看是否能找到增广路，即是否能找到右边的点为未匹配点，由于起始点也为未匹配点，所以在这条路径上，可以增加一对匹配点，怎么做呢？可知在这条增广路径上，未匹配边比匹配边多一条，所以我们就把未匹配边改为匹配边， 把匹配边改为未匹配边。这样，匹配数就+1了。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
const int INF = 2e9;
const int MOD = 1e9+;
const int MAXN = 1e3+; int uN, vN;
int M[MAXN][MAXN], ulink[MAXN], vlink[MAXN];
bool vis[MAXN], uvis[MAXN], vvis[MAXN]; bool dfs(int u)
{
for(int i = ; i<=vN; i++)
if(M[u][i] && !vis[i])
{
vis[i] = true;
if(vlink[i]==- || dfs(vlink[i]))
{
vlink[i] = u;
ulink[u] = i;
return true;
}
}
return false;
} int hungary()
{
int ret = ;
memset(ulink, -, sizeof(ulink));
memset(vlink, -, sizeof(vlink));
for(int i = ; i<=uN; i++)
{
memset(vis, , sizeof(vis));
if(dfs(i)) ret++;
}
return ret;
} //从左边的未匹配点走一遍试找增广路的路径，但是却不可能找到增广路，否则最大匹配数会增加。
//路径上的首边必为未匹配边，尾边必为匹配边，且两种边交替出现。
void hungary_tree(int u)
{
uvis[u] = true;
for(int i = ; i<=vN; i++)
if(M[u][i] && !vvis[i])
{
vvis[i] = true;
hungary_tree(vlink[i]);
}
} int main()
{
int m;
while(scanf("%d%d%d", &uN, &vN, &m)&& (uN || vN || m))
{
memset(M, false, sizeof(M));
for(int i = ; i<=m; i++)
{
int u, v;
scanf("%d%d", &u, &v); //不能连双向图， 为什么？
M[u][v] = true; //因为u代表横坐标，v代表纵坐标.
} int cnt = hungary();
printf("%d", cnt); memset(uvis, false, sizeof(uvis));
memset(vvis, false, sizeof(vvis));
for(int i = ; i<=uN; i++) if(ulink[i]==-) hungary_tree(i);
for(int i = ; i<=uN; i++) if(!uvis[i]) printf(" r%d", i);
for(int i = ; i<=vN; i++) if(vvis[i]) printf(" c%d", i);
printf("\n");
}
}