前言 这东西虽然我早就学过了,但是最近才发现我以前学的是假的,心中感慨万千(雾),故作此篇. 简介 带权二分图:每条边都有权值的二分图 最大权匹配:使所选边权和最大的匹配 KM算法,全称Kuhn-Munkres算法,是用于解决最大权匹配的一种算法. 根据我的理解,该算法算是一种基于贪心的松弛算法,它通过设置顶标将原问题转化为求一个完备匹配(完备匹配:匹配数=min(左部点数,右部点数)). 流程 设左部中点\(x\)的顶标\(wx_x\).右部中点\(y\)的顶标\(wy_y\).初始时\(wx

#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> #include<set> #include<stack> #def

题面: 羽毛球队有男女运动员各n人.给定2 个n×n矩阵P和Q.P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势:Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势.由于技术配合和心理状态等各种因素影响,P[i][j]不一定等于Q[j][i].男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i].设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大. 题解: 看完题很容易发现这就是一个带权二分图匹配,

POJ 2195 Going Home (带权二分图匹配) Description On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a

/* 带权二分图匹配 用费用流求,增加源点s 和 汇点t */ #include<bits/stdc++.h> using namespace std; #define maxn 10005 #define maxm 200005 ]; int head[maxn],tot,n,m,s,t,ans,maxflow; char mp[maxn][maxn]; vector<pair<int,int> >M,H; void add(int u,int v,int w,int

给个地图有人和房子 保证人==房子,每个人移动到房子处需要花费曼哈顿距离的代价 问让人都住在房子里最小代价 显然是个带权二分图最大匹配 转化成以一个网络,规定w是容量,c是代价 1.S向人连边,w=1,c=0 2.房子向T连边,w=1,c=0 3.人向房子连边 w=1,c=距离 #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<vector&g

题目大意 : n个人 做m道题,其中 每连续的n道必须由不同的人做 已知第i人做出第j题的概率为pij,求最大期望 思路:考虑每连续的n道题 都要n个人来做,显然想到了带权的二分图匹配 然后就是套模板了 代码: #include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h>

这是一道代码大题.一开始读错题意了,然后理解成直接看上去的那种相邻,然后想不通好久!!! 把不同联通的图分离出来,然后先预处理一下形成之后的相邻图的状态,然后根据01确定哪一些是需要更换状态的,然后建图,利用二分图KM算法去匹配最优方案.然后求出每一组更换的,利用原先已经求好的路径去储存答案. #include<bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; ; vector<pair<int, int

题目描述 小M发现,美食节共有n种不同的菜品.每次点餐,每个同学可以选择其中的一个菜品.总共有m个厨师来制作这些菜品.当所有的同学点餐结束后,菜品的制作任务就会分配给每个厨师.然后每个厨师就会同时开始做菜.厨师们会按照要求的顺序进行制作,并且每次只能制作一人份. 此外,小M还发现了另一件有意思的事情: 虽然这m个厨师都会制作全部的n种菜品,但对于同一菜品,不同厨师的制作时间未必相同.他将菜品用1, 2, ..., n依次编号,厨师用1, 2, ..., m依次编号,将第j个厨师制作第i种菜品的时

题目描述 • 一个 4 × 4 的 0/1 矩阵 • 每次可以交换相邻两个元素 • 求从初始状态到目标状态的最小交换次数 输入格式 前四行,每行一个长为 4 的 0/1 字符串,描述初始状态. 后四行,每行一个长为 4 的 0/1 字符串,描述目标状态. 输出格式 一行一个数,表示最小交换次数. 样例输入 1111 0000 1110 0010 1010 0101 1010 0101 样例输出 4 solution: 不得不说这确实是道好题,而且难度适中.看到此题为0/1字符串并且数据规模小(但

KM(Kuhn-Munkres)算法求带权二分图的最佳匹配 相关概念 这个算法个人觉得一开始时有点难以理解它的一些概念,特别是新定义出来的,因为不知道是干嘛用的.但是,在了解了算法的执行过程和原理后,这些概念的意义和背后的作用就渐渐的显示出来了.因此,先暂时把相关概念列出来,看看,有个大概印象就好,等到了解了算法的流程后,在看原理中会有这些概念,那个时候回来细看就好了. 完备匹配:定义 设G＝<V1,V2,E>为二部图,|V1|≤|V2|,M为G中一个最大匹配,且|M|＝|V1|,则称M为V1

Luogu 1559 运动员最佳匹配问题(带权二分图最大匹配) Description 羽毛球队有男女运动员各n人.给定2 个n×n矩阵P和Q.P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势:Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势.由于技术配合和心理状态等各种因素影响,P[i][j]不一定等于Q[j][i].男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i].设计一个算法,计算男女运动员最佳配对法,使各组男女双

HDU 2255 奔小康赚大钱(带权二分图最大匹配) Description 传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子. 这可是一件大事,关系到人民的住房问题啊.村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子. 另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比

先orz litble--KM算法 为什么要用KM算法 因为有的题丧心病狂卡费用流 KM算法相比于费用流来说,具有更高的效率. 算法流程 我们给每一个点设一个期望值[可行顶标] 对于左边的点来说,就是期望能匹配到多大权值的右边的点 对于右边的点来说,就是期望能在左边的点的期望之上还能产生多少贡献 两个点能匹配,当且仅当它们的期望值之和为这条边的权值 一开始初始化所有左点的期望是其出边的最大值,因为最理想情况下当然是每个点都匹配自己能匹配最大的那个 右点期望为0 然后我们逐个匹配,当一个点匹配失败

UVA1349 题意:给定一些有向带权边,求出把这些边构造成一个个环,总权值最小 解法: 对于带权的二分图的匹配问题可以用通过KM算法求解. 要求最大权匹配就是初始化g[i][j]为0,直接跑就可以: 要求最小权匹配就是初始化g[i][j]为-INF,加边的时候边权为负,最后输出答案的相反数. 因为要求每个点恰好属于一个圈,意味着每个点都有一个唯一的后继. 反过来,只要每个点都有唯一的后继,每个点一定属于某个圈. 唯一的是我们想到了二分图的概念,我们对于每个点,建立由u到v的二分图, 之后问题就

二分图的判定 如果一个图是连通的,可以用如下的染色法判定是否二分图: 我们把X部的结点颜色设为0,Y部的颜色设为1. 从某个未染色的结点u开始,做BFS或者DFS .把u染为0,枚举u的儿子v.如果v未染色,就染为与u相反的颜色,如果已染色,则判断u与v的颜色是否相同,相同则不是二分图. 如果一个图不连通,则在每个连通块中作判定. #include <bits/stdc++.h> const int maxn = 505; std::vector<int> e[maxn]; int

题目请戳这里 题目大意:给n个字符串,再给一个n的排列:p1,p2....pn.然后将第i个字符串贴到第pi个字符串后面,然后形成一个环.pi的首字符和第i个字符串的末尾字符就相邻,如果这2个字符相等,各自再向内延伸一个位置,知道这个环首尾字符不等为止.延伸的位置为该环的得分(如果pi == i,得分为0),对于每个排列,有n个这样的环,求得分和最大为多少. 题目分析:最大带权匹配!!以为是个字符串的题目,就没仔细看... 建图直接跑模版... 详情请见代码: #include <iostrea

博文“二分图的最大匹配.完美匹配和匈牙利算法”对二分图相关的几个概念讲的特别形象,特别容易理解.本文介绍部分主要摘自此博文. 还有其他可参考博文: 趣写算法系列之--匈牙利算法 用于二分图匹配的匈牙利算法 1.前言 二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图.准确地说:把一个图的顶点划分为两个不相交集 U 和V ,使得每一条边都分别连接U.V中的顶点.如果存在这样的划分,则此图为一个二分图.二分图的一个等价定义是:不含有「含奇数条边的环」的图.图

/** 题目:hdu2255 奔小康赚大钱 km算法 链接:http://acm.hdu.edu.cn/showproblem.php?pid=2255 题意:lv 思路:最优匹配(最大权完美匹配) km算法 模板来自:http://www.cnblogs.com/wenruo/p/5264235.html 如果是求最小权完美匹配,那么将所有权值取相反数,然后求得最大权,输出最大权的相反数即可. */ #include <iostream> #include <cstring> #

题目链接 奔小康赚大钱 Time Limit: 1000/1000MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7350 Accepted Submission(s): 3263 Problem Description 传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子. 这可是一件大事,关系到人民的住房问题啊.村里共有n间房间,刚好有n家老百姓,考虑到

How far away ? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 28961    Accepted Submission(s): 11639 Problem Description There are n houses in the village and some bidirectional roads connectin