題意：

　　P門課程，N個學生。給出每門課程的選課學生，求是否可以給每門課程選出一個課代表。課代表必須是選了該課的學生且每個學生只能當一門課程的。

題解：

　　匈牙利算法的入門題。

#include <iostream> #include <cstring> #include <cstdio> #include <vector> using namespace std; const int maxn = 1005; int t; int k, s; int flag; int p, n; int vis[maxn]; int match[maxn]; vector<int> g[maxn]; void init() {flag = 0;memset(match, -1, sizeof(match));for(int i = 1; i <= p+n; i++) g[i].clear(); } bool dfs(int u) {vis[u] = 1;for(int i = 0; i < g[u].size(); i++) {int v = g[u][i], w = match[v];if(w<0 || !vis[w]&&dfs(w)) {match[u] = v;match[v] = u;return true;}}return false; } int hungarian() {int res = 0;for(int u = 1; u <= s+p; u++) {if(match[u] < 0) {memset(vis, 0, sizeof(vis));if(dfs(u)) res++;}}return res; } int main() {scanf("%d", &t);while(t--) {init();scanf("%d%d", &p, &n);for(int i = 1; i <= p; i++) {scanf("%d", &k);if(!k) flag = 1;while(k--) {scanf("%d", &s);g[i].push_back(s+p);g[s+p].push_back(i); }}if(flag || n<p) {puts("NO");continue;}int ans = hungarian();if(ans == p) puts("YES");else puts("NO");} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Pneuis/p/8688618.html

總結(jié)

以上是生活随笔為你收集整理的POJ - 1469 COURSES （匈牙利算法入门题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。