威佐夫博弈
有两堆,若干个物品,两个人轮流从某一堆或从两堆中取同样多的物品,规定每次最少拿走一个,最多不限制,最后拿光的人获胜。
巴什博奕
有 $n$ 个物品,A, B两人轮流从物品中拿走一部分,每次至少拿 $1$ 个,最多拿 $?$ 个,拿走最后一个的人获胜。
是否有必胜策略,若有,则求出策略。
二分图 & 最大匹配 & 匈牙利算法
定义 二分图 对于一个无向图 $G=(V, E)$,可以将 $V$ 分为两个不相交的子集,使得任意一条边的顶点分属两个不同的点集,那么这个无向图是二分图。 匹配 对于无向图 $G=(V, E)$,取边集的子集 $E^*$,使得 $E^*$ 中任意两条边没有公共顶点,那么 $E^*$ 是图 $G$ 的一个匹配,又称边独立集。 最大匹配 边数最多的匹配…