| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 18454 | Accepted: 7275 |
Description
Input
Output
Sample Input
2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1
Sample Output
YES NO
Source
题目解读：p门课，n个学生. 接下来p行，每行代表第i门课每行先输入这门课的学生数，然后在一次输入这些学生的编号。通过匈牙利算法问：能不能保证每门课至少都有一个学生. 算法要点：最大匹配数>=课程数p ？
匈牙利算法 代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>g[310];
int link[310], vis[310];
int p, n;
bool match(int x)
{
for(int i=0; i<g[x].size(); i++ )
{
if(!vis[g[x][i]] )
{
vis[g[x][i]] = true;
if(link[g[x][i]]==-1 || match(link[g[x][i]]) )
{
link[g[x][i]] = x;
return true;
}
}
}
return false;
}
int hungary()
{
int tot=0;
memset(link, 255, sizeof(link));
for(int i=1; i<=n; i++)
{
memset(vis, 0, sizeof(vis));
if(match(i) )
{
tot++;
}
}
return tot;
}
int main()
{
int t;
int i, j, k;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &p, &n);
int dd, u;
for(i=1; i<=n; i++)
g[i].clear();
for(i=1; i<=p; i++)
{
scanf("%d", &dd);
while(dd--)
{
scanf("%d", &u);
g[u].push_back(i);
}
}
int ans = hungary();
if(ans >= p)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
Hopcroft-Karp 算法：
Hopcroft-Karp算法相比普通的匈牙利算法更快，所以当两边集合的点比较多时，为了快速完成匹配可以考虑这个算法，即使是有模板，但代码比较长且比较繁琐，容易写错。
敲的时候要特别注意！
H-K算法代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int p, n;
vector<int>g[310];
int n1, n2;
int mx[310], my[310];
queue<int>que;
int dx[310], dy[310];
bool vis[310];
bool find(int u)
{
for(int i=0; i<g[u].size(); i++)
{
if(!vis[g[u][i]] && dy[g[u][i]] == dx[u]+1 )
{
vis[g[u][i]] = true;
if(!my[g[u][i]] || find(my[g[u][i]]) )
{
mx[u] = g[u][i];
my[g[u][i]] = u;
return true;
}
}
}
return false;
}
int matching()
{
memset(mx, 0, sizeof(mx));
memset(my, 0, sizeof(my));
int ans=0;
while(true)
{
bool flag=false;
while(!que.empty())
que.pop();
memset(dx, 0, sizeof(dx));
memset(dy, 0, sizeof(dy));
for(int i=1; i<=n1; i++)
if(!mx[i] )
que.push(i);
while(!que.empty() )
{
int u=que.front();
que.pop();
for(int i=0; i<g[u].size(); i++ )
{
if(!dy[g[u][i]] )
{
dy[g[u][i]] = dx[u]+1;
if(my[g[u][i]])
{
dx[my[g[u][i]]] = dy[g[u][i]] + 1;
que.push(my[g[u][i]] );
}
else
flag=true;
}
}
}
if(!flag) break;
memset(vis, false, sizeof(vis));
for(int i=1; i<=n1; i++)
{
if(!mx[i] && find(i) )
ans++;
}
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
int dd, u;
while(t--)
{
scanf("%d %d", &p, &n);
for(int i=1; i<=n; i++)
g[i].clear();
for(int i=1; i<=p; i++)
{
scanf("%d", &dd);
while(dd--)
{
scanf("%d", &u);
g[u].push_back(i);
}
}
n1=n; n2=p;
int ans = matching();
if(ans >= p )
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
poj 1469 COURSES (二分图模板应用 【*模板】 )
原文：http://www.cnblogs.com/yspworld/p/4369404.html