博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Hdu 1083 Courses(匈牙利算法模版题)
阅读量:5234 次
发布时间:2019-06-14

本文共 1093 字,大约阅读时间需要 3 分钟。

题意:给你一个p表示测试组数,给你n和m表示课的个数和学生的个数,接下来n行首数字i表示该堂课的学生代表人数,之后为i个学生编码,问能否为每堂课找到一个学生课代表且不冲突;

题解:匈牙利算法模版

另附简单易懂匈牙利算法讲解:

#include
#include
const int N =305;using namespace std;bool h[N][N];bool vis[N];int link[N];int n,m;bool hungary(int x){ for(int i=1;i<=m;i++){ if(h[x][i]==1&&!vis[i]){ vis[i]=1; if(link[i]==-1||hungary(link[i])){ link[i]=x; return 1; } } } return 0;}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); memset(h,0,sizeof(h)); memset(link,-1,sizeof(link)); for(int i=1;i<=n;i++){ int u; scanf("%d",&u); while(u--){ int j; scanf("%d",&j); h[i][j]=1; } } int ans=0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(hungary(i))ans++; } if(ans==n)printf("YES\n"); else printf("NO\n"); } return 0;}

 

转载于:https://www.cnblogs.com/Mrleon/p/8444775.html

你可能感兴趣的文章
linux php编译安装
查看>>
name phone email正则表达式
查看>>
721. Accounts Merge
查看>>
「Unity」委托 将方法作为参数传递
查看>>
重置GNOME-TERMINAL
查看>>
redis哨兵集群、docker入门
查看>>
hihoCoder 1233 : Boxes(盒子)
查看>>
oracle中anyData数据类型的使用实例
查看>>
C++对vector里面的元素排序及取任意重叠区间
查看>>
软件测试——性能测试总结
查看>>
12.4站立会议
查看>>
Java Concurrentmodificationexception异常原因和解决方法
查看>>
客户端访问浏览器的流程
查看>>
codeforces水题100道 第二十二题 Codeforces Beta Round #89 (Div. 2) A. String Task (strings)
查看>>
c++||template
查看>>
[BZOJ 5323][Jxoi2018]游戏
查看>>
编程面试的10大算法概念汇总
查看>>
Vue
查看>>
python-三级菜单和购物车程序
查看>>
条件断点 符号断点
查看>>