二分图匹配的模板
二分图: 如果顶点集 V 可分割为两个互不相交的子集 X 和 Y, 并且图中每条边连接的两个顶点一个在 X 中, 另一个在 Y 中, 则称图 G 为二分图.
交替路: 从一个未匹配点出发, 依次经过非匹配边, 匹配边, 非匹配边... 形成的路径叫交替路
增广路: 两个端点都是未盖点的交替路叫做可增广路.
伪代码:
- bool(u)
- {
- for(u 所连的点)
- {
if v 不在交替路上
{
将 v 加入交替路
if v 点未匹配 || 有可能有增长路
{
标记;
- ture;
- }
- }
- }
- false;
- }
- #include<algorithm>
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<stack>
- #include<queue>
- #include<cmath>
- #include<set>
- #define ll long long
- #define mem(a,b) memset(a,b,sizeof(a))
- #define inf 0x3f3f3f3f
- using namespace std;
- const int maxn=3e4+10;
- struct edge{
- int u,v,next;
- }e[maxn*2];
- int g[maxn*2],vis[maxn*2],dis[maxn*2],cheek[maxn];
- int tot;
- void init()
- {
- mem(g,0);
- mem(vis,0);
- mem(e,0);
- mem(dis,0);
- tot=0;
- }
- void make_edge(int u,int v)
- {
- e[++tot]=(edge){u,v,g[u]};
- g[u]=tot;
- }
- bool dfs(int u)
- {
- for(int i=g[u];i>0;i=e[i].next)
- {
- int v=e[i].v;
- if(!cheek[v])// 如果 v 不在交替路上
- {
- cheek[v]=1;// 将 v 加入交替路
- if(!vis[v]||dfs(vis[v]))// 如果 v 点未被覆 || 有可能有增广路 标记
- {
- //vis[u]=v;
- vis[v]=u;
- return true;// 如果有增广路
- }
- }
- }
- return false;// 无
- }
- int hungarian(int n,int m)
- {
- int ans=0;
- for(int u=m+1;u<=n+m;u++)// 枚举一个集合的点
- {
- if(vis[u]==0)// 未被覆盖
- {
- mem(cheek,0);
- if(dfs(u)) ans++;// 匹配 ++;
- }
- }
- return ans;
- }
- int main(){
- int t;
- scanf("%d",&t);
- while(t--)
- {
- init();
- int n,m;
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- {
- int t;
- scanf("%d",&t);
- for(int j=1;j<=t;j++)
- {
- int now;
- scanf("%d",&now);
- make_edge(m+i,now);
- //make_edge(now,m+i);
- }
- }
- int temp=hungarian(n,m);
- //cout<<temp<<endl;
- cout<<(temp==n?"YES":"NO")<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2980776.html