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

本文共 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

你可能感兴趣的文章
【MySql】权限不足导致的无法连接到数据库以及权限的授予和撤销
查看>>
android实现gif图与文字混排
查看>>
hdu1384Intervals(差分约束)
查看>>
python 字符编码
查看>>
269D Maximum Waterfall
查看>>
C++11 多线程
查看>>
sed-加速你在Linux的文件编辑
查看>>
HttpServer发送数据到kafka
查看>>
phpcms站---去除域名绑定目录中的HTML
查看>>
20155303 2016-2017-2 《Java程序设计》第九周学习总结
查看>>
一次很失败的抄底
查看>>
数据结构C++(10)二叉树——链表实现(linkBinaryTree)
查看>>
利用Condition实现多线程交替执行
查看>>
里氏替换原则(设计模式原则2)
查看>>
lamp一键安装
查看>>
解决“iOS 7 app自动更新,无法在app中向用户展示更新内容”问题
查看>>
OpenCV——Haar-like特征
查看>>
HttpWebResponse发送post请求并接收
查看>>
python 相对路径和绝对路径的区别
查看>>
Day36 python基础--并发编程基础5
查看>>