当前位置: 代码迷 >> 综合 >> HDU1083 Courses——最大匹配裸题
  详细解决方案

HDU1083 Courses——最大匹配裸题

热度:11   发布时间:2024-02-12 11:08:36.0

点这里


题意: n个学生和p个课程,要求每个课程都有一个对应的课代表,并且一个学生只能担任一个课代表。如果这个最大匹配等于学生人数,则输出YES,否则输出NO。
题解: 就是一个最大匹配的裸题,题目看懂就能直接套模板,不会写的应该是模板不会用,建议先去学好匈牙利算法。


过程中犯的错:

  • 题意没有弄清楚,求最大匹配是毋庸置疑的,但我想当然地以为是最大匹配等于课程数量就可以了,(毕竟下意识认为多少课程就需要多少课代表咯),但是这个题目的要求是最大匹配等于学生人数才输出YES。
  • 模板不熟悉,我尝试着想背出模板,实际上我是偷瞄一眼模板写一句代码,写完了还有bug,二分图的题目做的太少了,今天是感觉有点忘记这类题目才找了一个简单题来做,实际上真的快要忘干净了。

#include<bits/stdc++.h>
using namespace std;
const int N = 610;int t, n, p, k, x;
int vis[N], match[N];
vector<int> v[N];
bool dfs(int u){for(int i = 0; i < v[u].size(); i++){int to = v[u][i];if(!vis[to]){vis[to] = 1;if(!match[to] || dfs(match[to])){match[to] = u;return true;}}}return false;
}int main(){scanf("%d", &t);while(t--){for(int i = 0; i < N; i++)	v[i].clear(), match[i] = 0;scanf("%d%d", &n, &p);for(int i = 1; i <= n; i++){scanf("%d", &k);while(k--){scanf("%d", &x);v[i].push_back(x);}}int sum = 0;for(int i = 1; i <= n; i++){memset(vis, 0, sizeof vis);if(dfs(i))	sum++;}if(sum == n)printf("YES\n");else		printf("NO\n");}return 0;
}