首页 > 代码库 > HLG1407Leyni的游戏【最小点权覆盖集】

HLG1407Leyni的游戏【最小点权覆盖集】

2024-07-17 00:56:02   215人阅读

大意：

给你一个n行m列的矩阵

1 2

1 1

每次操作可使一整行或一整列的一个数减少1（如果是0则不变）

问最少多少次操作会使所有的数变为零

 

分析：

该题很像poj消灭外星人的那道题

思路也差不很多

将x轴当左集合，y轴当右集合，边权值为所在点的数字

那么一条边就代表了矩阵中的一个点

只要找出最小的权值去覆盖所有的边就能把所有的数字变为零

也就是传说中的最小点权覆盖集

最小点权覆盖集 = 最大权匹配

KM跑一遍就可以了

但是需要注意的是如果两边点的个数不相等

那么我们用虚拟点代替就可以了

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 205; 7 const int INF = 1000000000; 8 int n; 9 10 int W[maxn][maxn];11 int Lx[maxn], Ly[maxn];12 int Left[maxn];13 bool S[maxn], T[maxn];14 15 bool match(int i) {16     S[i] = true;17     for(int j = 1; j <= n; j++) if(Lx[i] + Ly[j] == W[i][j] && !T[j]) {18         T[j] = true;19         if(!Left[j] || match(Left[j])) {20             Left[j] = i;21             return true;22         }23     }24     return false;25 }26 27 void update() {28     int a = INF;29     for(int i = 1; i <= n; i++) if(S[i])30         for(int j= 1; j <= n; j++) if(!T[j])31             a = min(a, Lx[i] + Ly[j] - W[i][j]);32     for(int i = 1; i <= n; i++) {33         if(S[i]) Lx[i] -= a;34         if(T[i]) Ly[i] += a;35     }36 }37 38 void KM() {39     for(int i = 1; i <= n; i++) {40         Left[i] = Lx[i] = Ly[i] = 0;41         for(int j = 1; j <= n; j++)42             Lx[i] = max(Lx[i], W[i][j]);43     }44     for(int i = 1; i<= n; i++) {45         for(;;) {46             for(int j = 1; j <= n; j++) S[j] = T[j] = 0;47             if(match(i)) break; else update();48         }49     }50 }51 52 int main() {53     int num;54     int m;55     while(EOF != scanf("%d %d",&n, &m)) {56         memset(W, 0, sizeof(W));57         for(int i = 1; i <= n; i++) {58             for(int j = 1; j <= m; j++) {59                 scanf("%d",&num);60                 W[i][j] = num;61             }62         }63         n = max(n, m);64         KM();65         int ans = 0;66         for(int i = 1; i <= n; i++) {67             ans += Lx[i] + Ly[i];68         }69         printf("%d\n",ans);70     }71     return 0;72 }
View Code

网络流代码：

  1 #include <iostream>  2 #include <queue>  3 #include <cstdio>  4 #include <cstring>  5 #include <vector>  6 using namespace std;  7   8 const int maxn = 200 * 200 + 10;  9 const int INF = 1000000000; 10  11 struct Edge { 12     int from, to, cap, flow, cost; 13 }; 14  15 struct MCMF 16 { 17     int n, m, s, t; 18     vector<Edge> edges; 19     vector<int> G[maxn]; 20  21     int inq[maxn]; 22     int d[maxn]; 23     int p[maxn]; 24     int a[maxn]; 25  26     void init(int n) { 27         this -> n = n; 28         for(int i = 0; i < n; i++) G[i].clear(); 29         edges.clear(); 30     } 31  32     void AddEdge(int from, int to, int cap, int cost) { 33         edges.push_back((Edge) { from, to, cap, 0, cost } ); 34         edges.push_back((Edge) { to, from, 0, 0, -cost } ); 35         m = edges.size(); 36         G[from].push_back(m - 2); 37         G[to].push_back(m - 1); 38     } 39  40     bool BellmanFord(int s, int t, int &flow, int &cost) { 41         for(int i = 0; i < n; i++) d[i] = INF; 42         memset(inq, 0, sizeof(inq) ); 43         d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; 44         queue<int> Q; 45         Q.push(s); 46         while(!Q.empty()) { 47             int u = Q.front(); Q.pop(); 48             inq[u] = 0; 49             for(int i = 0; i < G[u].size(); i++) { 50                 Edge &e = edges[G[u][i]]; 51                 if(e.cap > e.flow && d[e.to] > d[u] + e.cost) { 52                     d[e.to] = d[u] + e.cost; 53                     p[e.to] = G[u][i]; 54                     a[e.to] = min(a[u], e.cap - e.flow); 55                     if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } 56                 } 57             } 58         } 59  60         if(d[t] == INF) return false; 61         flow += a[t]; 62         cost += d[t] * a[t]; 63         int u = t; 64         while(u != s) { 65             edges[p[u]].flow += a[t]; 66             edges[p[u] ^ 1].flow -= a[t]; 67             u = edges[p[u]].from; 68         } 69         return true; 70     } 71  72     int MinCost(int s, int t) { 73         //this -> s = s; this -> t = t; 74         int flow = 0, cost = 0; 75         while(BellmanFord(s, t, flow, cost)){}; 76         return cost; 77     } 78 }; 79  80 MCMF g; 81  82 int main() { 83     int n, m; 84     int num; 85     while(EOF != scanf("%d %d",&n, &m)) { 86         int s = 0; int t = n + m + 1; 87         g.init(n * m + 10); 88         for(int i = 1; i <= n; i++) { 89             for(int j = 1; j <= m; j++) { 90                 scanf("%d",&num); 91                 g.AddEdge(i, j + n, 1,-num); 92             } 93         } 94         for(int i = 1; i <= n; i++) { 95             g.AddEdge(s, i, 1, 0); 96         } 97         for(int j = 1; j <= m; j++) { 98             g.AddEdge(j + m, t, 1, 0); 99         }100         printf("%d\n",-g.MinCost(s, t));101     }102     return 0;103 }
TLE

 


联系
我们