博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 2853 (KM最大匹配)
阅读量:5960 次
发布时间:2019-06-19

本文共 877 字,大约阅读时间需要 2 分钟。

题目链接:

题目大意:二分图匹配费用流。①最大匹配②最小原配变动

解题思路

如果去掉第二个要求,那么就是裸KM。

然而加上第二个要求,那么就需要一种新的建图方式。

建图

对于输入矩阵,每一条边,cost扩大K倍($K=n+1$)

对于原配,每一条边cost在扩大K倍基础上+1

KM

统计cost时,直接把cost整除K,然后累加。

并且Hash一下原配边的变动情况。

扩大K倍的作用

准确来说,K倍是为了+1而存在的。由于要优先考虑原配边,所以cost要大些。

但是,加大的cost又要使得最后好统计真实的cost。所以选择扩大K倍,然后整除K,这样,+1会被直接舍掉。

K=n+1是防止n=1的情况被卡姿势。

代码

#include "iostream"#include "cstdio"#include "cstring"#include "algorithm"using namespace std;#define maxn 55int n,m,Hash[maxn],tmp,old,K;int link[maxn],LX[maxn],RX[maxn],W[maxn][maxn],slack[maxn],e[maxn][maxn];bool S[maxn],T[maxn];const int inf=0x3f3f3f3f;bool dfs(int u){    S[u]=true;    for(int v=1;v<=m;v++)    {        if(T[v]) continue;        int t=LX[u]+RX[v]-W[u][v];        if(!t)        {            T[v]=true;            if(!link[v]||dfs(link[v]))            {                link[v]=u;                return true;            }        }        else if(t

 

转载地址:http://ttuax.baihongyu.com/

你可能感兴趣的文章
Java 集合框架查阅技巧
查看>>
apache配置虚拟主机
查看>>
CollectionView水平和竖直瀑布流的实现
查看>>
前端知识复习一(css)
查看>>
spark集群启动步骤及web ui查看
查看>>
利用WCF改进文件流传输的三种方式
查看>>
Spring学习总结(2)——Spring的常用注解
查看>>
关于IT行业人员吃的都是青春饭?[透彻讲解]
查看>>
钱到用时方恨少(随记)
查看>>
mybatis主键返回的实现
查看>>
org.openqa.selenium.StaleElementReferenceException
查看>>
数论之 莫比乌斯函数
查看>>
linux下查找某个文件位置的方法
查看>>
python之MySQL学习——数据操作
查看>>
Harmonic Number (II)
查看>>
长连接、短连接、长轮询和WebSocket
查看>>
day30 模拟ssh远程执行命令
查看>>
做错的题目——给Array附加属性
查看>>
Url.Action取消字符转义
查看>>
HBase 笔记3
查看>>