专栏首页Zaqdt_ACMPOJ 3041 Asteroids(匈牙利算法)

POJ 3041 Asteroids(匈牙利算法)

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

AC代码:

#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 条评论
登录 后参与评论

相关文章

  • HDU 3829 Cat VS Dog(二分图最大独立集)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3829

    Ch_Zaqdt
  • 最少联通代价(dfs+曼哈顿距离)

    现在要把这 2 个连通块连通, 求最少需要把几个’.’转变成’X’。上图的例子中, 最少只需要把 3个’.’转变成’X’。下图用’*’表示转化为’X’的格点...

    Ch_Zaqdt
  • NYOJ 116 士兵杀敌(二) (线段树+树状数组)

    题目链接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=116

    Ch_Zaqdt
  • Data Structure_Visualization

    选择排序很简单,遍历所有元素,查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程,可以用不同颜色代表排...

    西红柿炒鸡蛋
  • leetcode 88 Merge Sorted Array

    Given two sorted integer arrays nums1 and nums2, merge nums2 intonums1 as one so...

    用户1539362
  • 剑指Offer - 面试题13. 机器人的运动范围(BFS/DFS)

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(...

    Michael阿明
  • HDU 2389 二分图最大匹配之Hopcroft-Karp优化 O(n^0.5*m)

    T个测试用例, 时间time, n个人,接下来n行是坐标 和 每个人的速度 v。 m,接下来m行是 雨伞的坐标。

    用户2965768
  • 06--图解数据结构之并查集

    张风捷特烈
  • 洛谷P1966 火柴排队(逆序对)

    首先要保证权值最小,不难想到一种贪心策略,即把两个序列中rank相同的数放到同一个位置

    attack
  • 图论建图

    图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券