二分图匹配问题

匈牙利算法

二分图顾名思义,对于其定义不再赘述

匈牙利算法是我们解决二分图最大匹配的通常途径,算法流程如下:

  • 对于一个节点$u$进行匹配
  • 如果节点$u$连向$v$并且$v$没有匹配,使$v$匹配$u$
  • 如果$v$已匹配,则对于$v$的原先匹配进行尝试

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline bool DFS(int u)
{
for ( int i = Begin[u]; i; i = Next[i] )
{
int v = To[i];
if ( vis[v] ) continue ;
vis[v] = true;
if ( !link[v] || DFS(link[v]) )
{
link[v] = u;
return true;
}
}
return false;
}

[SCOI2010]连续攻击游戏

题目链接

起初思路为对于装备$i$的两个属性$a_i,b_i$构建二分图,但发现很难处理这两个属性不能同时使用

后来发现可以将所有装备的属性放在左边,装备的编号放在右边

即对于$(a_i,i)$和$(b_i,i)$连边,然后求二分图最大匹配即可