二分图匹配——poj1469
2024-10-01 02:23:09
关于本题二分图的匹配
关系始终是加单向边
用左边去匹配右边,match表示的是右边的人匹配的对应的左边的点
/*
关于本题二分图的匹配
链接的关系始终是单向边
用左边去匹配右边,match表示的是右边的人匹配的对应的左边的点
*/ #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 505
int mp[maxn][maxn],match[maxn];
bool vis[maxn];
int p,n; bool dfs(int x){//第x门课是否有人匹配
for(int i=;i<=n;i++){
if(!vis[i] && mp[x][i]){//枚举每门课可以选择的人
vis[i]=;
//第i个人已经匹配了match[i]课
if(match[i]==-||dfs(match[i])){
match[i]=x;return ;
}
}
}
return ;
}
int sum(){
int res=;
for(int i=;i<=p;i++){//每门课是否有学生来匹配
memset(vis,,sizeof vis);
if(dfs(i))res++;
}
return res;
}
void init(){
memset(match,-,sizeof match);
memset(mp,,sizeof mp);
}
int main(){
int t;cin>>t;
while(t--){
init();
cin>>p>>n;//p门课,n个学生
for(int i=;i<=p;i++){//喜欢第i门课的学生有k个
int k,j;scanf("%d",&k);
while(k--){
scanf("%d",&j);
mp[i][j]=;
}
}
int ans=sum();
if(ans==p)puts("YES");
else puts("NO");
}
}
最新文章
- jQuery链式操作[转]
- CentOs下jdk的安装
- POJ 2155 Matrix(二维树状数组+区间更新单点求和)
- BZOJ3170: [Tjoi 2013]松鼠聚会
- Android应用性能优化之使用SQLiteStatement优化SQLite操作
- 无责任Windows Azure SDK .NET开发入门篇三[使用Azure AD 管理用户信息--3.3 Details用户详细信息]
- qt creator中使用qwt插件
- Shell until循环
- fs.rename可以重新写入文件
- uml系列(三)——用例图
- C#表达式和语句
- 解题(DirGraCheckPath--有向图的遍历(深度搜索))
- lsb隐写
- redis ERR This instance has cluster support disabled
- Python编程-数据库-利用PyMysql访问windows下的MySql数据库
- (素材源代码) 猫猫学iOS 之UIDynamic重力、弹性碰撞吸附等现象牛逼Demo
- sencha touch 可自动增长高度TextArea
- Codeforces 374 C. Travelling Salesman and Special Numbers (dfs、记忆化搜索)
- C++构造函数后面的冒号
- PHP双向队列,双端队列代码