题面
农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。不幸的是，由于工程问题，每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。
给出奶牛们的爱好的信息，计算最大分配方案。
题意
如题面。
题解
每只奶牛只喜欢在自己喜欢的牛棚里面产奶。（匹配）
一个牛棚只能容纳一头奶牛。
最大的分配方案。
匈牙利算法(匹配算法)，个人感觉实质上就是一个DFS的匹配算法。
伪代码：
bool dfs(int x)
{
while(找到Xi的关联顶点Yj){
if(顶点Yj不在增广路径上){
将Yj加入增广路
if(Yj是未覆盖点或者Yj的原匹配点Xk能找到增广路径){ //扩充集合M
将Yj的匹配点改为Xi;
返回true;
}
}
返回false;
}
根据题意可以知道这是一道匈牙利算法的模板题。于是开始根据伪代码来造代码。
代码
代码1(my code)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
const int maxm = 10010;
int n,m,tong[maxm],ans;
bool vis[maxn],love[maxn][maxm];
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void init()
{
cin >> n >> m;
for(int i=1;i<=n;i++){
int l=read();
while(l--){
love[i][read()]=true;
}
}
}
bool dfs(int x)
{
for(int i = 1;i <= m;++i)
{
if(!vis[i] && love[x][i])
{
vis[i] = true;
if(tong[i]==0 || dfs(tong[i]))
{
tong[i] = x;
return true;
}
}
}
return false;
}
int main(int argc, char const *argv[])
{
init();
for(int i = 1;i <= n;++i)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
cout << ans;
return 0;
}
代码2(rank 1)
#include <cstdio>
#include <cstring>
using namespace std;
#define M(x) memset(x, false, sizeof(x))
const int maxn = 205;
int N, M, ans, link[maxn];
bool vis[maxn], A[maxn][maxn];
bool dfs(int x){
for(int i = 1; i <= N; i++)
if(A[x][i] && !vis[i]){
vis[i] = true;
if(!link[i] || dfs(link[i])){
link[i] = x;
return true;
}
}
return false;
}
inline int GetInt(){
char x;
int ret;
while((x = getchar()) < '0' || x > '9');
ret = x - '0';
while((x = getchar()) >= '0' && x <= '9') ret = ret * 10 + x - '0';
return ret;
}
int main(){
N = GetInt(), M = GetInt();
for(int i = 1; i <= N; i++){
int sum;
sum = GetInt();
for(int j = 1, OP; j <= sum; j++){
OP = GetInt();
A[i][OP] = true;
}
}
for(int i = 1; i <= N; i++){
M(vis);
if(dfs(i)) ans++;
}
printf("%d", ans);
return 0;
}