NYOJ 237 游戏高手的烦恼 POJ3041-Asteroids ( 二分图的最大匹配 )

2024-08-27 02:58

本文主要是介绍NYOJ 237 游戏高手的烦恼 POJ3041-Asteroids ( 二分图的最大匹配 ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:

NYOJ 237  游戏高手的烦恼:click here~~

POJ  3041 Asteroids           :click here~~

题意:

两题一样,翻译不同而已。

有一位传说级游戏高手,在闲暇时间里玩起了一个小游戏,游戏中,一个n*n的方块形区域里有许多敌人,玩家可以使用炸弹炸掉某一行或者某一列的所有敌人。他是种玩什么游戏都想玩得很优秀的人,所以,他决定,使用尽可能少的炸弹炸掉所有的敌人。

现在给你一个游戏的状态,请你帮助他判断最少需要多少个炸弹才能炸掉所有的敌人吧。

比如说,下图中X表示敌人

X . X 
. X . 

. X . 

则,他只需要炸掉第1行与第2列就能炸掉所有的敌人,所以只需要两颗炸弹就可以了。

输入
第一行是一个整数T,表示测试数据的组数(0<T<=400)。
每组测试数据的第一行有两个整数n,K,其中n表示游戏方形区域的大小。(n<=500,K<=10 000)
随后的K行,每行有两个整数i,j表示第i行,第j列有一个敌人(行和列都从1开始编号)。(1<=i,j<=n)
输出
对于每组测试数据,输出一个整数表示最少需要的炸弹颗数
样例输入
1
3 4
1 1
1 3
2 2
3 2
样例输出
2
思路:

把炸弹攻击路径当作图的顶点,而把敌人当作连接路径对应的边,转化之后,攻击路径方案即对应一个顶点集合S,而要求炸弹能炸掉所有的敌人,换言之,就是构图后每一条边都至少有一个属于S的端点,如此,问题转化成求最小满足上述要求的顶点集合S。,而每个敌人所在位置对应的边,都分别与一个水平方向和一个竖直方向的顶点相连,把每一列当成一个点,每一行当成一个点,若行节点和列节点之间有边,则表明该行列该列有一个敌人。因此是二分图,运用二分图的匹配,此题还设计二分图最小点集覆盖=二分图最小匹配,相关算法知识不懂可以自学资料。

图例:

更详细的最小点覆盖数 = 最大匹配数思路:参考:click here

代码:

 
#include <math.h>
#include <queue>
#include <deque>
#include <vector>
#include <stack>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>using namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
const int maxn=502;
struct Edge
{int v;
};
int n, k;
vector <int >  mapp[maxn];
int vis[maxn], connect[maxn];
int dfs(int u)
{int i;for(i =0; i<mapp[u].size(); i++){int xx=mapp[u][i];if(!vis[xx]){vis[xx] =1;if (!connect[xx]|| dfs(connect[xx])){connect[xx] = u;return 1;}}}return 0;
}
int main()
{//freopen("1.txt","r",stdin);//freopen("2.txt","w",stdout);int cas;scanf("%d",&cas);while(cas--){int sum=0;scanf("%d%d", &n, &k);for (int i =0; i <maxn; i++) mapp[i].clear();for (int i =1; i <=k; i++){int a, b;scanf("%d%d", &a, &b);mapp[a].push_back(b);}memset(connect,0, sizeof(connect));for(int i =1; i <=n; i++){memset(vis, 0, sizeof(vis));if (dfs(i))sum++;}printf("%d\n",sum);}return 0;
}

优化代码():

 
#include <stdio.h>
#include <string.h>const int N = 505;
const int M = 10005;struct Vertex
{int head;
}V[N];struct Edge
{int v,next;
}E[M];int top,match[N];bool used[N];void Init()
{top = 0;memset(V,-1,sizeof(V));memset(match,0,sizeof(match));
}void Add_Edge(int u,int v)
{E[top].v = v;E[top].next = V[u].head;V[u].head = top++;
}bool dfs(int u)
{for(int i=V[u].head;~i;i=E[i].next){int v = E[i].v;if(!used[v]){used[v] = true;if(!match[v] || dfs(match[v])){match[v] = u;return true;}}}return false;
}int maxMatch(int n)
{int ans = 0;for(int i=1;i<=n;i++){memset(used,false,sizeof(used));if(dfs(i))++ans;}return ans;
}int main()
{int z,n,m,num;scanf("%d",&z);while(z--){Init();scanf("%d%d",&n,&m);while(m--){int i,j;scanf("%d%d",&i,&j);Add_Edge(i,j);}printf("%d\n",maxMatch(n));}return 0;
}

When you want to give up, think of why you persist until now!




这篇关于NYOJ 237 游戏高手的烦恼 POJ3041-Asteroids ( 二分图的最大匹配 )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110440

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta