二分图

参考资料

• 二分图 - OI Wiki
• 二分图最大匹配 - OI Wiki

匈牙利算法

147 Bcpp

bool match(int u)
{
	for(auto v:G[u])
	{
		if(vis[v])continue;
		vis[v]=1;
		if(!a[v]||match(a[v]))
		{
			a[v]=u;
			return 1;
		}
	}
	return 0;
}

例题

洛谷 P3386 【模板】二分图最大匹配

给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

洛谷 P10937 車的放置

给定一个 $N$ 行 $M$ 列的棋盘，已知某些格子禁止放置。

问棋盘上最多能放多少个不能相互攻击的車。

車放在格子里，攻击范围与中国象棋的「車」一致。