首页 > 代码库 > POJ3041Asteroids【最小点覆盖】

POJ3041Asteroids【最小点覆盖】

2024-07-16 13:55:18   220人阅读

大意：

X.X 
.X. 
.X.     如左图X代表怪物你可以用激光去消灭它们，一次可以消灭同一行或同一列的所有怪物，问最少多少次才可以把所有怪物消灭完

 

思路：把x，y坐标分别看成左集合与右集合，若两个坐标有联系就建一条边

最后求得是最小点覆盖

正确性证明：每个怪物的坐标都是由一对x，y确定的，在二分图中每条边就代表一对坐标点，所以只要把所有的边被覆盖就可以了

 

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <set> 6 using namespace std; 7  8 const int maxn = 505; 9 10 struct Node {11     int to, next;12 }p[10005];13 14 int head[10005];15 16 int tot;17 18 int X[maxn];19 int x_cnt;20 int vis[maxn];21 int link[maxn];22 23 void AddEdge(int u, int v) {24     p[tot].to = v;25     p[tot].next = head[u];26     head[u] = tot ++;27 }28 29 bool Find(int u) {30     for(int i = head[u]; i; i = p[i].next) {31         int v = p[i].to;32         if(!vis[v]) {33             vis[v] = 1;34             if(link[v] == -1 || Find(link[v])) {35                 link[v] = u;36                 return true;37             }38         }39     }40     return false;41 }42 int n;43 44 int solve() {45     int cnt = 0;46     memset(link, -1, sizeof(link));47     memset(vis, 0, sizeof(vis));48     if(Find(X[0])) cnt++;49     for(int i = 1; i < x_cnt; i++) {50         if(X[i] == X[i - 1]) continue;51         memset(vis, 0, sizeof(vis));52         if(Find(X[i])) cnt++;53     }54     return cnt;55 }56 57 int main() {58     int k;59     int u, v;60     //freopen("3041.txt","r",stdin);61     while(EOF != scanf("%d %d",&n, &k)) {62         tot = 1;63         x_cnt = 0;64         memset(head, 0, sizeof(head));65         //memset(X, 0, sizeof(X));66         for(int i = 0; i < k; i++) {67             scanf("%d %d",&u, &v);68             AddEdge(u, v);69             X[x_cnt++] = u;70         }71         sort(X, X + x_cnt);72         printf("%d\n",solve());73     }74     return 0;75 }
View Code

 


联系
我们