Uva 11419 我是SAM

题目链接：https://vjudge.net/problem/UVA-11419

题意：一个网格里面有一些目标，可以从某一行，某一列发射一发子弹，可以打穿；

求最少的子弹，和在哪里打？

分析：

听说可以用吗MCMF做，没多想；

一个目标，拆成两个点，X,Y，X与Y之间连一条边，现在，在这些点里面选出一些点，使得每一条边都有一个端点被覆盖，这就是最小点覆盖=最大匹配（证明在之前写过，博客里可以找到，证明很有意思）；

然后还要找出哪些被覆盖了；

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <vector>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 const int maxn = 1000 + 5; // 单侧顶点的最大数目
  8 
  9 // 二分图最大基数匹配
 10 struct BPM
 11 {
 12     int n, m;               // 左右顶点个数
 13     vector<int> G[maxn];    // 邻接表
 14     int left[maxn];         // left[i]为右边第i个点的匹配点编号，-1表示不存在
 15     bool T[maxn];           // T[i]为右边第i个点是否已标记
 16 
 17     int right[maxn];        // 求最小覆盖用
 18     bool S[maxn];           // 求最小覆盖用
 19 
 20     void init(int n, int m)
 21     {
 22         this->n = n;
 23         this->m = m;
 24         for(int i = 0; i < n; i++) G[i].clear();
 25     }
 26 
 27     void AddEdge(int u, int v)
 28     {
 29         G[u].push_back(v);
 30     }
 31 
 32     bool match(int u)
 33     {
 34         S[u] = true;
 35         for(int i = 0; i < G[u].size(); i++)
 36         {
 37             int v = G[u][i];
 38             if (!T[v])
 39             {
 40                 T[v] = true;
 41                 if (left[v] == -1 || match(left[v]))
 42                 {
 43                     left[v] = u;
 44                     right[u] = v;
 45                     return true;
 46                 }
 47             }
 48         }
 49         return false;
 50     }
 51 
 52     // 求最大匹配
 53     int solve()
 54     {
 55         memset(left, -1, sizeof(left));
 56         memset(right, -1, sizeof(right));
 57         int ans = 0;
 58         for(int u = 0; u < n; u++)   // 从左边结点u开始增广
 59         {
 60             memset(S, 0, sizeof(S));
 61             memset(T, 0, sizeof(T));
 62             if(match(u)) ans++;
 63         }
 64         return ans;
 65     }
 66 
 67     // 求最小覆盖。X和Y为最小覆盖中的点集
 68     int mincover(vector<int>& X, vector<int>& Y)
 69     {
 70         int ans = solve();
 71         memset(S, 0, sizeof(S));
 72         memset(T, 0, sizeof(T));
 73         for(int u = 0; u < n; u++)
 74             if(right[u] == -1) match(u); // 从所有X未盖点出发增广
 75         for(int u = 0; u < n; u++)
 76             if(!S[u]) X.push_back(u); // X中的未标记点
 77         for(int v = 0; v < m; v++)
 78             if(T[v]) Y.push_back(v);  // Y中的已标记点
 79         return ans;
 80     }
 81 };
 82 
 83 BPM solver;
 84 
 85 int R, C, N;
 86 
 87 int main()
 88 {
 89     int kase = 0;
 90     while(scanf("%d%d%d", &R, &C, &N) == 3 && R && C && N)
 91     {
 92         solver.init(R, C);
 93         for(int i = 0; i < N; i++)
 94         {
 95             int r, c;
 96             scanf("%d%d", &r, &c);
 97             r--;
 98             c--;
 99             solver.AddEdge(r, c);
100         }
101         vector<int> X, Y;
102         int ans = solver.mincover(X, Y);
103         printf("%d", ans);
104         for(int i = 0; i < X.size(); i++) printf(" r%d", X[i]+1);
105         for(int i = 0; i < Y.size(); i++) printf(" c%d", Y[i]+1);
106         printf("
");
107     }
108     return 0;
109 }

View Code