题目链接：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了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <string> 6 #include <vector> 7 #include <map> 8 #include <set> 9 #include <queue> 10 #include <sstream> 11 #include <algorithm> 12 using namespace std; 13 const int INF = 2e9; 14 const int MOD = 1e9+7; 15 const int MAXN = 1e3+10; 16 17 int uN, vN; 18 int M[MAXN][MAXN], ulink[MAXN], vlink[MAXN]; 19 bool vis[MAXN], uvis[MAXN], vvis[MAXN]; 20 21 bool dfs(int u) 22 { 23 for(int i = 1; i<=vN; i++) 24 if(M[u][i] && !vis[i]) 25 { 26 vis[i] = true; 27 if(vlink[i]==-1 || dfs(vlink[i])) 28 { 29 vlink[i] = u; 30 ulink[u] = i; 31 return true; 32 } 33 } 34 return false; 35 } 36 37 int hungary() 38 { 39 int ret = 0; 40 memset(ulink, -1, sizeof(ulink)); 41 memset(vlink, -1, sizeof(vlink)); 42 for(int i = 1; i<=uN; i++) 43 { 44 memset(vis, 0, sizeof(vis)); 45 if(dfs(i)) ret++; 46 } 47 return ret; 48 } 49 50 //从左边的未匹配点走一遍试找增广路的路径，但是却不可能找到增广路，否则最大匹配数会增加。 51 //路径上的首边必为未匹配边，尾边必为匹配边，且两种边交替出现。 52 void hungary_tree(int u) 53 { 54 uvis[u] = true; 55 for(int i = 1; i<=vN; i++) 56 if(M[u][i] && !vvis[i]) 57 { 58 vvis[i] = true; 59 hungary_tree(vlink[i]); 60 } 61 } 62 63 int main() 64 { 65 int m; 66 while(scanf("%d%d%d", &uN, &vN, &m)&& (uN || vN || m)) 67 { 68 memset(M, false, sizeof(M)); 69 for(int i = 1; i<=m; i++) 70 { 71 int u, v; 72 scanf("%d%d", &u, &v); //不能连双向图， 为什么？ 73 M[u][v] = true; //因为u代表横坐标，v代表纵坐标. 74 } 75 76 int cnt = hungary(); 77 printf("%d", cnt); 78 79 memset(uvis, false, sizeof(uvis)); 80 memset(vvis, false, sizeof(vvis)); 81 for(int i = 1; i<=uN; i++) if(ulink[i]==-1) hungary_tree(i); 82 for(int i = 1; i<=uN; i++) if(!uvis[i]) printf(" r%d", i); 83 for(int i = 1; i<=vN; i++) if(vvis[i]) printf(" c%d", i); 84 printf(" "); 85 } 86 }