POJ 3041 Asteroids(匈牙利算法)

2019-01-08 09:47:39 浏览数 (1)

       题意就是有一个地图,然后给你几个点的坐标标记为'x',然后你有一个武器,每次可以消灭一行或一列的'x',问最少需要几次能把所有的'x'消灭完。然后我们可以构建一个二分图,然后这就是一个最小覆盖集问题,最小覆盖数 = 最大匹配数,根据匈牙利算法就能求了。先上代码,以后再补详细的解释。

AC代码:

代码语言:javascript复制
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int b[10005];
int vis1[10005];
int vis[10005][10005];
int n,m,sum;

bool Find(int x){
  for(int i=1;i<=n;i  ){
    if(vis[x][i] && !vis1[i]){
      vis1[i] = 1;
      if(b[i] == 0 || Find(b[i])){
        b[i] = x;
        return true;
      }
    }
  }
  return false;
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=0;i<m;i  ){
    int x,y;
    cin>>x>>y;
    vis[x][y] = 1;
  }
  sum = 0;
  memset(b,0,sizeof(b));
  for(int i=1;i<=n;i  ){
    memset(vis1,0,sizeof(vis1));
    if(Find(i))sum  ;
  }
  cout<<sum<<endl;
  return 0;
}

0 人点赞