二分图最大带权匹配。 输入点的个数和各边权值，输出最大匹配的权值和。 1 #include<iostream>2 #include<cstdio>3 #include<cstring>4 5 using namespace std;6 7 const int N=310;8 const int INF=0x3f3f3f3f;9 10 int n,nx,ny; 11 int linker[N],lx[N],ly[N],slack[N]; //lx,ly为顶标，nx,ny分别为x点集y点集的个数 12 int visx[N],visy[N],w[N][N]; 13 14 int DFS(int x){ 15 visx[x]=1; 16 for(int y=1;y<=ny;...
完备匹配，X集合中每个都有匹配，或Y集合中每个都有匹配。 最佳匹配，权值和最大的完备匹配称为最佳匹配。 添加一些边权为0的边，就能将最大权匹配和最佳匹配统一起来。 KM算法流程，我们假定X集合大小不超过Y集合。 开始X集合每个点给一个标签，值为其最大相邻边边权，Y集合每个点标签为0。 如果一条边的两个端点的标签和为边权，则认为这条边是可用的。我们每次在可用边上做匈牙利算法，如果找到匹配边则退出，找下一个点的匹配边...
原文链接：http://www.cnblogs.com/ACAC/archive/2010/05/17/1737729.html/*pku 2195 KM算法求最小权二分匹配*/#include<stdio.h>#include<string.h>#include<math.h>#define MAX 101int hx[MAX],mx[MAX],hy[MAX],my[MAX];char map[MAX][MAX];int usedx[MAX],usedy[MAX],match[MAX],w[MAX][MAX],n,m;//// match[]存放的右顶点的匹配信息,w[][]存放的是权值,N是右顶点数int lx[MAX],ly[MAX],slack[MAX];// lx[],ly[]分别存放的是左右...
原文链接：http://www.cnblogs.com/ACAC/archive/2010/05/17/1737667.htmlPOJ 2195(KM算法) 转自大牛,牛人天天有,就是没有我啊这是一个典型的最大匹配的题目，题目意思是给出一些房子和一些人，每个人到每个房子都有一个相应的代价，最后要求怎么安排这些人，房子和人一一配对，使最后的代价最小。方法是KM算法，是一个求最大（最小)匹配的一个很强大的算法。不过这种题目还可以用费用流来做。下面是某牛的对KM算法讲解http://hi.b...
http://acm.hdu.edu.cn/showproblem.php?pid=2255 传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。 这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。 另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕...
二分图定义 图的顶点恰好可以分成两个集合，同一个集合内的顶点间不允许有边，处在不同集合的顶点允许有边相连。 问题分类 最大匹配问题：匈牙利算法、Hopcroft–Karp算法 最优权值匹配问题：Kuhn-Munkras算法 关键思想 增广路（augmenting path）：假设目前已有一个匹配结果，存在一组未匹配定点的OD，能够找到一条路径，这条路径上匹配和未匹配的定点交替出现，称为增广路 增广路上的匹配和未匹配取反，则匹配数增加1。 KM算法 基...
layout: post title: 训练指南 UVALive - 4043（二分图匹配 + KM算法） author: "luowentaoaa" catalog: true mathjax: true tags: - 二分图匹配 - 图论 - 训练指南Ants UVALive - 4043 题意 给你n个白点和n个黑点的平面坐标，要求用n条不相交的线连起来，每条线段连一个白点和黑点，每个点连一条线，也就是匹配。让你输出第i个白点所对应的黑点。 思路 二分图完美匹配问题。但是题目中有个线段不相交，怎么办？其实这个最佳完美匹...
KM算法详解+模板 大佬讲的太好了！！！太好了！！！ http://www.cnblogs.com/wenruo/p/5264235.html KM算法用来求二分图最大权完美匹配。 本文配合该博文服用更佳：趣写算法系列之--匈牙利算法 本文没有给出KM算法的原理，只是模拟了一遍算法的过程。另，博主水平较差，发现问题欢迎指出，谢谢！！！！ 现在有N男N女，有些男生和女生之间互相有好感，我们将其好感程度定义为好感度，我们希望把他们两两配对，并且最后希望好感...