首页 > 代码库 > Uva 11419 我是SAM

Uva 11419 我是SAM

2024-09-18 23:47:22   205人阅读

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

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

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

 

分析：

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

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

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

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

 

Uva 11419 我是SAM


联系
我们