二分图的匈牙利算法 HDU 2063(裸模板,待增加)

2023-11-24 22:30

本文主要是介绍二分图的匈牙利算法 HDU 2063(裸模板,待增加),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

过山车

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16742    Accepted Submission(s): 7314


Problem Description
RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了。可是,过山车的每一排只有两个座位,而且还有条不成文的规矩,就是每个女生必须找个个男生做partner和她同坐。但是,每个女孩都有各自的想法,举个例子把,Rabbit只愿意和XHD或PQK做partner,Grass只愿意和linle或LL做partner,PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题,boss刘决定只让找到partner的人去坐过山车,其他的人,嘿嘿,就站在下面看着吧。聪明的Acmer,你可以帮忙算算最多有多少对组合可以坐上过山车吗?

Input
输入数据的第一行是三个整数K , M , N,分别表示可能的组合数目,女生的人数,男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行,每行有两个数,分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。

Output
对于每组数据,输出一个整数,表示可以坐上过山车的最多组合数。

Sample Input
  
6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0

Sample Output

3

匈牙利算法:寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

代码如下:最裸的模板:

#include <stdio.h>
#include <string.h>int k,m,n;
int map[505][505];
int vis[505];
int lianxi[505];
int suan(int x)//对于男生来说:有机会就上(lianxi[j]==0),没有机会创造机会也要上(suan(lianxi[j]))
{for(int j=1; j<=n; j++){if(!vis[j]&&map[x][j])//该男生没被匹配,并且女生愿意跟他匹配{vis[j]=1;if(lianxi[j]==0||suan(lianxi[j]))//如果女生没有匹配着或者匹配着了以后又可以改成别的匹配{lianxi[j]=x;return 1;}}}return 0;
}
int main()
{while(scanf("%d",&k)!=EOF){if(k==0)break;scanf("%d%d",&m,&n);memset(map,0,sizeof(map));memset(lianxi,0,sizeof(lianxi));while(k--){int a,b;scanf("%d%d",&a,&b);map[a][b]=1;}int count=0;for(int i=1; i<=m; i++){memset(vis,0,sizeof(vis));if(suan(i))count++;}printf("%d\n",count);}
}


 Problem 2232 炉石传说

Accept: 3    Submit: 5
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

GG学长虽然并不打炉石传说,但是由于题面需要他便学会了打炉石传说。但是传统的炉石传说对于刚入门的GG学长来说有点复杂,所以他决定自己开发一个简化版的炉石传说。

在简化版的炉石传说中:

每个随从只有生命值和攻击力,并且在你的回合下,你的每只随从在本回合下只能选择一个敌方随从进行攻击。当两个随从a,b交战时,a的生命值将减去b的攻击力,b的生命值将减去a的攻击力,(两个伤害没有先后顺序,同时结算)。如果a或b的生命值不大于0,该随从将死亡。

某一次对局中,GG学长和对手场面上均有n个随从,并且是GG学长的回合。由于GG学长是个固执的boy,他一定要在本回合杀死对方所有随从,并且保证自己的随从全部存活。他想知道能否做到。

 Input

第一行为T,表示有T组数据。T<=100。

每组数据第一行为n,表示随从数量(1 <= n <= 100)

接下来一行2 * n个数字a1, b1, a2, b2, ... , an, bn (1 <= ai, bi <= 100)

表示GG学长的n个随从,ai表示随从生命,bi表示随从攻击力

接下来一行2 * n个数字c1, d1, c2, d2, ... , cn, dn (1 <= ci, di <= 100)

表示对手的n个随从,ci表示随从生命,di表示随从攻击力。

 Output

每组数据,根据GG是否能完成他的目标,输出一行”Yes”或”No”。

 Sample Input

234 4 5 5 6 61 1 2 2 3 334 4 5 5 6 61 4 2 4 3 4

 Sample Output

YesNo

 Source

福州大学第十三届程序设计竞赛
代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
#include<math.h>typedef struct
{int xue;int gong;
} node;
node a[105];
node b[105];int vis[105];
int link[105];
int n;int pan(node a,node b)
{if(a.xue>b.gong&&a.gong>=b.xue)return 1;return 0;
}
int pipei(int x){for(int i=1; i<=n; i++){if(vis[i]==0&&pan(a[x],b[i])){vis[i]=1;if(link[i]==0||pipei(link[i])){link[i]=x;return 1;}}}return 0;}
int main()
{int test;scanf("%d",&test);while(test--){scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d%d",&a[i].xue,&a[i].gong);}for(int i=1; i<=n; i++){scanf("%d%d",&b[i].xue,&b[i].gong);}
//        for(int i=1;i<=n;i++)
//            printf("%d %d ",a[i].xue,a[i].gong);
//        printf("\n");
//          for(int i=1;i<=n;i++)
//            printf("%d %d ",b[i].xue,b[i].gong);
//        printf("\n");int sum=0;memset(link,0,sizeof(link));for(int i=1; i<=n; i++){memset(vis,0,sizeof(vis));if(pipei(i)){sum++;}}if(sum==n)printf("Yes\n");else printf("No\n");}
}


这篇关于二分图的匈牙利算法 HDU 2063(裸模板,待增加)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

SpringBoot项目使用MDC给日志增加唯一标识的实现步骤

《SpringBoot项目使用MDC给日志增加唯一标识的实现步骤》本文介绍了如何在SpringBoot项目中使用MDC(MappedDiagnosticContext)为日志增加唯一标识,以便于日... 目录【Java】SpringBoot项目使用MDC给日志增加唯一标识,方便日志追踪1.日志效果2.实现步

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系