题目大意:求二分图的最优匹配(首先数目最大, 其次权值最大)。解题关键:KM算法复杂度:$O(n^3)$#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
usingnamespace std;
typedef longlong ll;
constint N=310;
constint inf=0x3f3f3f3f;
int nx,ny;
int g[N][N];
int match[N],lx[N],ly[N];//y中各点匹配状态,x,y中的顶点标号int slack[N];
bool visx[N],visy[N]...
传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子。另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价...
http://acm.hdu.edu.cn/showproblem.php?pid=4862选t<=k次,t条路要经过所有的点一次并且仅仅一次,建图是问题:
我自己最初就把n*m 个点分别放入X集合以及Y集合,再求最优匹配,然后连样例都过不了,而且其实当时解释不了什么情况下不能得到结果,因为k此这个条件相当于没用上。。。建图方法:
1、X集合和Y集合都放入n*m+k个点,X中前n*m个点和Y中前n*m个点之间,如果格子里的值相等,权就是(收益-耗费),不等就是(-耗费),因...
KM算法 1 #include <bits/stdc++.h>2#define N 15003#define inf 9999999994usingnamespace std;5int a[N],bs[N],nx=0,ny=0,k;6int linky[N],lx[N],ly[N],slack[N];7int visx[N],visy[N],w[N][N];8int min(int a,int b){return (a<b)?a:b;}9int find(int x){
10 visx[x]=1;
11for(int y=1;y<=ny;y++){
12if(visy[y]) continue;
13int t=lx[x]+ly[y]-w[x][y];
14if(t==0){visy[y]=1;
15if(linky[y]==-1||find(linky[y])){
16 ...
二分图最大权值匹配问题。用KM算法。最小权值的时候把权值设置成相反数 1/*--------------------------------------------------------------------------------------*/ 2 3 #include <algorithm>4 #include <iostream>5 #include <cstring>6 #include <ctype.h>7 #include <cstdlib>8 #include <cstdio>9 #include <vector>10 #include <string>11 #include <queue>12 #include <stack>13 #include <cmath>14 #include <set>1...
1//hdu1853 2 #include<stdio.h>3 #include<string.h>4#define INF 999999995int map[103][103],pr[103],pl[103],visr[103],visl[103],slack[103],match[103];6int n,m;7int dfs(int u)8{9int i,j,val;10 11 visl[u]=1;12for(i=1;i<=n;i++)13 {14if(!visr[i])15 {16 val=pr[i]+pl[u]-map[u][i];17if(val==0)18 {19 visr[i]=1;20if(match[i]==-1||dfs(match[i]))21 ...
【POJ 2195】 Going Home(KM算法求最小权匹配)Going HomeTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 20303 Accepted: 10297DescriptionOn 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 $1 travel fee for everystep he moves, until he ...
传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子。另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价...
KM算法计算带权二分图最优匹配
时间复杂度\(O(n^3)\)
模板题:hdu2255 奔小康赚大钱
const int maxn=310;
const int inf=0x3f3f3f3f;int n;
int g[maxn][maxn],ex1[maxn],ex2[maxn],match[maxn],slack[maxn];
bool vis1[maxn],vis2[maxn];bool dfs(int x){vis1[x]=true;for(int y=0;y<n;y++) {if(vis2[y]) continue; int gap=ex1[x]+ex2[y]-g[x][y];if(gap==0){ vis2[y]=true;if(match[y]==-1 || dfs(match[y])){ match[y]=...
题目链接:[传送门](https://www.luogu.com.cn/problem/UVA11383)
## 分析
这道题乍看上去没有思路,但是我们仔细一想就会发现这道题其实是一个二分图最大匹配的板子
我们可以把这道题想象成将男生和女生之间两两配对,使他们的好感度最大
我们把矩阵中的元素$a[x][y]$看成女生$x$和男生$y$之间的好感度,跑一个KM算法
因为KM算法会维护$ex_{}boy[x] + ex_{}girl[y]>=love[y][x]$,所以最后的结果就是我们想要的
注意有多组数据
##...
二分图[匈牙利算法 & KM算法]
概念二分图:把一个图的顶点划分为两个不相交集 U 和V ,使得每一条边都分别连接U、V中的顶点。如果存在这样的划分,则此图为一个二分图。匹配:在图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点。例如,图 3、图 4 中红色的边就是图 2的匹配。我们定义匹配点、匹配边、未匹配点、非匹配边,例如图 3 中 1、4、5、7 为匹配点,其他顶点为未匹配点;(1,5)、(4,7)为匹配...
二分图最大带权匹配。
输入点的个数和各边权值,输出最大匹配的权值和。 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...