nyoj--239--月老的难题(最小点覆盖)
2024-08-23 09:34:19
月老的难题
时间限制:1000 ms | 内存限制:65535 KB
难度:4
- 描述
-
月老准备给n个女孩与n个男孩牵红线,成就一对对美好的姻缘。
现在,由于一些原因,部分男孩与女孩可能结成幸福的一家,部分可能不会结成幸福的家庭。
现在已知哪些男孩与哪些女孩如果结婚的话,可以结成幸福的家庭,月老准备促成尽可能多的幸福家庭,请你帮他找出最多可能促成的幸福家庭数量吧。
假设男孩们分别编号为1~n,女孩们也分别编号为1~n。
- 输入
- 第一行是一个整数T,表示测试数据的组数(1<=T<=400)
每组测试数据的第一行有两个整数n,K,其中男孩的人数与女孩的人数都是n。(n<=500,K<=10 000)
随后的K行,每行有两个整数i,j表示第i个男孩与第j个女孩有可能结成幸福的家庭。(1<=i,j<=n) - 输出
- 对每组测试数据,输出最多可能促成的幸福家庭数量
- 样例输入
-
1
3 4
1 1
1 3
2 2
3 2 - 样例输出
-
2
- 来源
- 经典题目
-
上传者
匈牙利算法模板
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>map[550];
int pipei[550],used[550];
int find(int x)
{
int y;
for(int i=0;i<map[x].size();i++)
{
y=map[x][i];
if(!used[y])
{
used[y]=1;
if(!pipei[y]||find(pipei[y]))
{
pipei[y]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
map[i].clear();
pipei[i]=0;
}
int x,y,sum=0;
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
map[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
sum+=find(i);
}
printf("%d\n",sum);
}
return 0;
}
最新文章
- phpexcel 导出 科学计数问题
- map和list遍历基础
- 扩展GridView控件——为内容项添加拖放及分组功能
- [转发]Linux的系统调用宏
- ssh增加密匙登录
- ubuntu文件夹右键没有共享选项
- Android开发之Action Bar
- word2vec c代码使用说明
- 018 关联映射文件中<;class>;标签中的lazy(懒加载)属性
- 锁对象Lock
- 【Swift】IOS开发中自定义转场动画
- Spring揭秘 读书笔记 五 容器的启动
- python-tqdm进度条
- DOM编程以及domReady加载的几种方式
- JsRender练习总结
- 使用GSON工具实现json和其他数据格式间转换
- 008_python内置语法
- 微信开发】【Asp.net MVC】-- 微信分享功能
- 当try-catch-finally代码块遇上return,代码执行流程是怎样
- Spring cloud的Maven插件(二):run目标