电影兑换券的推荐策略——二分图最优匹配算法_UTF_8

新杰电磁阀模块

动手点关注干货不迷路问题概述一笔订单最多可使用所含电影票数目张兑换券。换而言之，用户选了几个座位，最多便能使用几张兑换券，兑换券有三个属性，分别是：面值（元）：在不支持补差的情况下，票价小于等于面值才可以使用固定支付金额（元）：满足兑换券的使用条件下，需要支付的钱。补差（是 / 否）：如果支持补差，当票价大于面值时，还需要额外支付 （票价 - 面值）元举个栗子：小明有一张面值 50，固定支付 19 元且支持补差的兑换券。那么他能使用这张兑换券去购买票价小于等于 50 元的电影票，只需支付 19 元。因为支持补差，所以他能购买票价为 60 元（大于面值）的电影票，需支付（19 + （ 60 - 50））既 29 元。我们问题是：用户下了一笔订单，订单中有 x（根据业务场景，x 匹配边->非匹配边->......->非匹配边 的路径。有的博客也叫交错路）的边取补边，来增加一条匹配边km 依赖定理及证明定理：如果二分图存在某组可行顶标，并且该可行顶标的相等子图存在完美匹配，那么该匹配就是原二分图的最佳匹配。证明：考虑原二分图的任意一组完美匹配 M ，其边权和 val(M)等于每条匹配边（匹配边没有公共顶点）的权值和，又根据可行顶标的定义，我们可以得出任意一组完美匹配的边权和都小于等于任意一组可行顶标的点权和。如果存在一组可行顶标且该可行顶标的相等子图存在完美匹配，那么该相等子图的完美匹配 M'的边权和 val(M')如下。（因为相等子图只存在 w(u, v) = l(u) + l(v) 的边）显然对于任意的完美匹配 M，val(M) #include#includeusingnamespacestd;constintMAXN=305;constintINF=0x3f3f3f3f;intlove[MAXN][MAXN];//记录每个妹子和每个男生的好感度intex_girl[MAXN];//每个妹子的期望值intex_boy[MAXN];//每个男生的期望值boolvis_girl[MAXN];//记录每一轮匹配匹配过的女生boolvis_boy[MAXN];//记录每一轮匹配匹配过的男生intmatch[MAXN];//记录每个男生匹配到的妹子如果没有则为-1intslack[MAXN];//记录每个汉子如果能被妹子倾心最少还需要多少期望值intN;booldfs(intgirl){vis_girl[girl]=true;for(intboy=0;boy