uva 11419(二分图最大匹配--最小点覆盖)

题意：有一个矩阵中放置的一写东西，然后你有一门炮，每次能横向或纵向开一炮，是这一行所有的东西摧毁。问你最少花多少炮弹摧毁所有的东西？输出一组解

思路：构建二分图，两遍结点是行和列。若（x，y）存在东西则建边。这样问题就转化为最小点覆盖=最大匹配。坑爹之处在与输出一组解，liurujia说从X中所有未盖点出发扩展匈牙利树，标记树中所有点，那么X中无标记点和Y中有标记点即为答案。一开始由于不知道什么是匈牙利树，wa了好多次。其实匈牙利树就是书上的所有路径都是匹配边与非匹配边间隔。

代码如下：

  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-02-26 21:50
  5  * Filename     : uva_11419.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22 
 23 using namespace std;
 24 typedef long long ll;
 25 typedef pair<int, int> pii;
 26 typedef pair<unsigned int,unsigned int> puu;
 27 typedef pair<int, double> pid;
 28 typedef pair<ll, int> pli;
 29 typedef pair<int, ll> pil;
 30 
 31 const int INF = 0x3f3f3f3f;
 32 const double eps = 1E-6;
 33 const int LEN = 1010;
 34 int Map[LEN][LEN], uN, vN, m, vis[LEN], link[LEN], tlink[LEN], visu[LEN], visv[LEN];
 35 int indu[LEN], indv[LEN];
 36 
 37 bool dfs(int u){
 38     for(int i=0; i<vN; i++){
 39         if(Map[u][i] && !vis[i]){
 40             vis[i] = 1;
 41             if(link[i] == -1 || dfs(link[i])){
 42                 link[i] = u;
 43                 tlink[u] = i;
 44                 return true;
 45             }
 46         }
 47     }
 48     return false;
 49 }
 50 
 51 int hungary(){
 52     int ret = 0;
 53     memset(link, -1, sizeof link);
 54     memset(tlink, -1, sizeof tlink);
 55     for(int i=0; i<uN; i++){
 56         memset(vis, 0, sizeof vis);
 57         if(dfs(i)) ret++;
 58     }
 59     return ret;
 60 }
 61 
 62 bool dtree(int u){
 63     visu[u] = 1;
 64     for(int i=0; i<vN; i++){
 65         if(Map[u][i] && !visv[i]){
 66             visv[i] = 1;
 67             if(link[i] == -1 || dtree(link[i])){
 68                 return true;
 69             }
 70         }
 71     }
 72     return false;
 73 }
 74 
 75 int main()
 76 {
 77 //    freopen("in.txt", "r", stdin);
 78 
 79     int a, b;
 80     while(scanf("%d%d%d", &uN, &vN, &m)!=EOF){
 81         if(!uN && !vN && !m) break;
 82         memset(Map, 0, sizeof Map);
 83         memset(visv, 0, sizeof visv);
 84         memset(visu, 0, sizeof visu);
 85         memset(indu, 0, sizeof indu);
 86         memset(indv, 0, sizeof indv);
 87         for(int i=0; i<m; i++){
 88             scanf("%d%d", &a, &b);
 89             a--;b--;
 90             indu[a] = indv[b] = 1;
 91             Map[a][b] = 1;
 92         }
 93         int ans = hungary();
 94         printf("%d", ans);
 95         //构造最小点覆盖的解
 96         for(int i=0; i<uN; i++) if(tlink[i] == -1)dtree(i);
 97         for(int i=0; i<uN; i++) if(!visu[i] && indu[i]) printf(" r%d", i+1);
 98         for(int i=0; i<vN; i++) if(visv[i] && indv[i]) printf(" c%d", i+1);
 99         printf("
");
100     }
101     return 0;
102 }

View Code

奔跑吧！少年！趁着你还年轻