http://poj.org/problem?id=1469
这道题我绝壁写过但是以前没有mark过二分图最大匹配的代码mark一下。
匈牙利 O(mn)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
#define LL long long
const int maxn=;
int n,m;
struct nod{
int y,next;
}e[maxn*maxn];
int head[maxn]={},tot=;
int p[maxn]={},vis[maxn]={};
inline void init(int x,int y){e[++tot].y=y;e[tot].next=head[x];head[x]=tot;}
bool dfs(int x){
for(int i=head[x];i;i=e[i].next){
if(!vis[e[i].y]){
vis[e[i].y]=;
if((!p[e[i].y])||dfs(p[e[i].y])){
p[e[i].y]=x;
return ;
}
}
}return ;
}
int main(){
int T;scanf("%d",&T);
while(T-->){
scanf("%d%d",&n,&m);
memset(p,,sizeof(p));
memset(vis,,sizeof(vis));
memset(head,,sizeof(head));tot=;
int x,y;
for(int i=;i<=n;i++){
scanf("%d",&x);
for(int j=;j<=x;j++){scanf("%d",&y);init(i,y);}
}
int ans=;
for(int i=;i<=n;i++){memset(vis,,sizeof(vis));if(dfs(i))++ans;}
if(ans==n)printf("YES\n");
else printf("NO\n");
}
return ;
}
hopcroft-karp O(sqrt(n)m)
https://blog.csdn.net/wall_f/article/details/8248373
是一种魔改版匈牙利，魔改之后竟然有点像网络流。不过我用网络流找最大匹配差不多也是这个复杂度吧，这个算法有什么意义吗。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
#define LL long long
const int maxn=;
const int minf=;
int n,m,dis;
struct nod{
int y,next;
}e[maxn*];
int head[maxn]={},tot=;
int vis[maxn]={};
int cx[maxn]={},cy[maxn]={},dx[maxn]={},dy[maxn]={};
inline void init(int x,int y){e[++tot].y=y;e[tot].next=head[x];head[x]=tot;}
bool bfs(){
memset(dx,-,sizeof(dx));memset(dy,-,sizeof(dy));
dis=minf;queue<int>q;
for(int i=;i<=n;i++){if(!cx[i]){q.push(i);dx[i]=;}}
while(!q.empty()){
int x=q.front();q.pop();
if(dx[x]>dis)break;
for(int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(dy[y]==-){
dy[y]=dx[x]+;
if(!cy[y])dis=dy[y];
else {dx[cy[y]]=dy[y]+;q.push(cy[y]);}
}
}
}
return dis!=minf;
}
int dfs(int x){
for(int i=head[x];i;i=e[i].next){
int y=e[i].y;
if((!vis[y])&&dy[y]==dx[x]+){
vis[y]=;
if(cy[y]&&dy[y]==dis)continue;
if((!cy[y])||dfs(cy[y])){
cy[y]=x;cx[x]=y;
return ;
}
}
}
return ;
}
int main(){
int T;scanf("%d",&T);
while(T-->){
scanf("%d%d",&n,&m);
memset(head,,sizeof(head));tot=;
int x,y;
for(int i=;i<=n;i++){
scanf("%d",&x);
for(int j=;j<=x;j++){scanf("%d",&y);init(i,y);}
}
int ans=;
memset(cx,,sizeof(cx));
memset(cy,,sizeof(cy));
while(bfs()){
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++){
if(!cx[i])ans+=dfs(i);
}
}
if(ans==n)printf("YES\n");
else printf("NO\n");
}
return ;
}