首页 > 其他 > 详细

POJ3041 Asteroids

时间:2020-07-07 16:40:58      阅读:49      评论:0      收藏:0      [点我收藏+]

gate

用时:看了题解之后20min左右吧...

给一个\(N\times N\)的网格,有\(k\)个障碍物,每次可以消灭一行或一列的障碍物,问至少几次可以清空。
把横、纵分为两个点集,每个障碍物\((i,j)\)即在\(i,j\)连一条边。
\(Konig定理\):最小覆盖数 = 最大匹配数
求二分图匹配即可。

code

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

const int maxn = 505;
int n,k,x,y,ans,cp[maxn];
bool vis[maxn],to[maxn][maxn];

bool find(int x){
    for(int i = 1;i <= n;i++)
        if(to[x][i] && !vis[i]){
            vis[i] = true;
            if(!cp[i] || find(cp[i])){
                cp[i] = x;
                return true;
            }
        }
    return false;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= k;i++){
        scanf("%d%d",&x,&y);
        to[x][y] = true;
    }
    for(int i = 1;i <= n;i++){
        memset(vis,0,sizeof(vis));
        if(find(i)) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

POJ3041 Asteroids

原文:https://www.cnblogs.com/mogeko/p/13261340.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!