标签:二分图最大匹配

【题解】 「网络流 24 题」最小路径覆盖 二分图最大匹配 LOJ – 6002

1. 题目

传送门= ̄ω ̄=

2. 题解

DAG的最小不相交路径覆盖问题

算法:把原图的每个点V拆成Vx和Vy两个点,如果有一条有向边A->B,那么就加边Ax−>By。这样就得到了一[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 「网络流 24 题」搭配飞行员 二分图最大匹配 LOJ – 6000

1. 题目

传送门= ̄ω ̄=

2. 题解

二分图最大匹配裸题

网络流偷懒打了匈牙利。

代码:

Read MoreComment

【题解】 The Perfect Stall POJ – 1274

传送门= ̄ω ̄=

思路:二分图最大匹配模板题。二分图最大匹配详见我的“二分图最大匹配”博客。

代码:

Read MoreComment

【题解】UOJ #78 二分图最大匹配

二分图匹配模板题,跑一遍增广路即可求得配对数和配对方案。详细看我写的那个二分图最大匹配= ̄ω ̄=
传送门

代码:

Read MoreComment

【算法】 二分图最大匹配

1.二分图最大匹配的定义

二分图匹配的定义:

给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。——百度百科

而二分[......]

[继续阅读= ̄ω ̄=]

Read MoreComment