二分图匹配的模板
二分图:如果顶点集 V可分割为两个互不相交的子集X和Y,并且图中每条边连接的两个顶点一个在 X中,另一个在 Y中,则称图G为二分图。
交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路
增广路:两个端点都是未盖点的交替路叫做可增广路。
伪代码:
bool(u)
{
for(u所连的点)
{
if v不在交替路上
{
将v加入交替路
if v点未匹配||有可能有增长路
{
标记;
ture;
}
}
}
false;
}
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<stack> 6 #include<queue> 7 #include<cmath> 8 #include<set> 9 10 11 #define ll long long 12 #define mem(a,b) memset(a,b,sizeof(a)) 13 #define inf 0x3f3f3f3f 14 15 using namespace std; 16 17 const int maxn=3e4+10; 18 19 struct edge{ 20 int u,v,next; 21 }e[maxn*2]; 22 23 int g[maxn*2],vis[maxn*2],dis[maxn*2],cheek[maxn]; 24 int tot; 25 26 void init() 27 { 28 mem(g,0); 29 mem(vis,0); 30 mem(e,0); 31 mem(dis,0); 32 tot=0; 33 } 34 35 void make_edge(int u,int v) 36 { 37 e[++tot]=(edge){u,v,g[u]}; 38 g[u]=tot; 39 } 40 41 bool dfs(int u) 42 { 43 for(int i=g[u];i>0;i=e[i].next) 44 { 45 int v=e[i].v; 46 if(!cheek[v])//如果v不在交替路上 47 { 48 cheek[v]=1;//将v加入交替路 49 if(!vis[v]||dfs(vis[v]))//如果v点未被覆||有可能有增广路 标记 50 { 51 //vis[u]=v; 52 vis[v]=u; 53 return true;//如果有增广路 54 } 55 } 56 } 57 return false;//无 58 } 59 60 int hungarian(int n,int m) 61 { 62 int ans=0; 63 for(int u=m+1;u<=n+m;u++)//枚举一个集合的点 64 { 65 if(vis[u]==0)//未被覆盖 66 { 67 mem(cheek,0); 68 if(dfs(u)) ans++;//匹配++; 69 } 70 } 71 return ans; 72 } 73 74 int main(){ 75 int t; 76 scanf("%d",&t); 77 while(t--) 78 { 79 init(); 80 int n,m; 81 scanf("%d%d",&n,&m); 82 for(int i=1;i<=n;i++) 83 { 84 int t; 85 scanf("%d",&t); 86 for(int j=1;j<=t;j++) 87 { 88 int now; 89 scanf("%d",&now); 90 make_edge(m+i,now); 91 //make_edge(now,m+i); 92 } 93 } 94 int temp=hungarian(n,m); 95 //cout<<temp<<endl; 96 cout<<(temp==n?"YES":"NO")<<endl; 97 } 98 return 0; 99 }