五个小镇被道路网连接，每两个小镇之间恰好有一条路。现给每条路都指定单一方向，求满足条件的指派数，使得任意两个起点、终点小镇之间都存在道路联通（可以经过其它小镇）
【难度】
【出处】
2017年第35届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
544
【解析】
显然，若存在一个小镇，与其相连的道路是“全进”或“全出”的，则显然不满足条件。于是每个小镇至少有一条“进路”和一条“出路”。显然图存在长度不小于 $3$ 的环。我们根据最长环分成以下情况讨论：
1．该环长度为 $5$，显然任两个小镇均可通过绕环到达。
2．该环长度为 $4$，环上 $4$ 个小镇两两之间可达。不在环上的小镇与环连接的道路有一进一出。所以其与环上任意小镇之间可达。
3．该环长度为 $3$，我们设不在环上的小镇为 $A$ 和 $B$ 。不妨设 $A,B$ 之间道路的方向为 $A\to B$ 。则有一条从环上出发指向 $A$ 的道路，有一条从 $B$ 上出发指向环的道路。易知任两个小镇之间可达
于是我们知道任两小镇可达的充要条件是每个小镇至少有一条“进路”和 一条“出路”
我们用总数减去不满足条件的图得到答案。
总共有 ${{2}^{\left(\begin{smallmatrix}
5 \\
2
\end{smallmatrix}\right)}}={{2}^{10}}$ 种图。存在“全进”或“全出”顶点的图有 $5\cdot{{2}^{6}}\cdot 2-5\cdot 4\cdot {{2}^{3}}$ 个。则满足条件的图有 ${{2}^{10}}-\left(5\cdot {{2}^{6}}\cdot 2-5\cdot 4\cdot {{2}^{3}} \right)=544$ 个
1．该环长度为 $5$，显然任两个小镇均可通过绕环到达。
2．该环长度为 $4$，环上 $4$ 个小镇两两之间可达。不在环上的小镇与环连接的道路有一进一出。所以其与环上任意小镇之间可达。
3．该环长度为 $3$，我们设不在环上的小镇为 $A$ 和 $B$ 。不妨设 $A,B$ 之间道路的方向为 $A\to B$ 。则有一条从环上出发指向 $A$ 的道路，有一条从 $B$ 上出发指向环的道路。易知任两个小镇之间可达
于是我们知道任两小镇可达的充要条件是每个小镇至少有一条“进路”和 一条“出路”
我们用总数减去不满足条件的图得到答案。
总共有 ${{2}^{\left(\begin{smallmatrix}
5 \\
2
\end{smallmatrix}\right)}}={{2}^{10}}$ 种图。存在“全进”或“全出”顶点的图有 $5\cdot{{2}^{6}}\cdot 2-5\cdot 4\cdot {{2}^{3}}$ 个。则满足条件的图有 ${{2}^{10}}-\left(5\cdot {{2}^{6}}\cdot 2-5\cdot 4\cdot {{2}^{3}} \right)=544$ 个
答案
解析
备注
