首页 > 代码库 > hdu 1083 最大匹配
hdu 1083 最大匹配
题意:N个学生 P 个课程 求最大匹配
3 3 //学生 课程 3 1 2 3 //课程1 匹配学生1 2 3 2 1 2 1 1
典型的匹配没什么好说的
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include<iostream> using namespace std; int p,n; int map[500][500]; int pre[500]; int v[500]; int dfs( int k) { for ( int i=1;i<=p;i++) { if (v[i]||!map[i][k]) //第i个人已经被上一个k课程给匹配了 continue ; v[i]=1; if (pre[i]==-1||dfs(pre[i])) { pre[i]=k; return 1; } } return 0; } int main() { int t,x,y,count,i,j; cin>>t; while (t--) { cin>>p>>n; memset (map,0, sizeof (map)); memset (pre,-1, sizeof (pre)); for (i=1;i<=p;i++) { cin>>x; for (j=1;j<=x;j++) { cin>>y; map[i][y]=1; } } count=0; for (i=1;i<=n;i++) { memset (v,0, sizeof (v)); if (dfs(i)) count++; } if (count==p) cout<< "YES" <<endl; else cout<< "NO" <<endl; } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。