HDU_2255 二分图最佳完美匹配 KM匈牙利算法

一开始还没看懂这个算法,后来看了陶叔去年的PPT的实例演示才弄懂

用一个lx[]和ly[]来记录X和Y集合中点的权值,有个定理是 lx[i]+ly[j]==w[i][j](边权值) 则该点是最佳匹配,因为首先
那个不等式肯定要>=的,否则就不满足题意了,如果是>则可以去匹配更有价值的边或者把权值降下来让匹配边的潜力更大。

所以只有把握了这个条件,其他就是走一遍最大匹配数。以及up()函数用来在无法匹配的时候,进行其他点的权值降低(也可以说是增广路的搜索)来得到匹配。


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 310
using namespace std;
int w[N][N],n,lx[N],ly[N],lefts[N];
bool S[N],T[N];
bool dfs(int u)
{
S[u]=1;
for (int v=1;v<=n;v++)
if (lx[u]+ly[v]==w[u][v] && !T[v]){
T[v]=true;
if (!lefts[v] || dfs(lefts[v])){
lefts[v]=u;
return true;
}
}
return false;
}
void update()
{
int a=1<<30;
for (int i=1;i<=n;i++) if (S[i])
for (int j=1;j<=n;j++) if (!T[j]){
a=min(a,lx[i]+ly[j]-w[i][j]);
}
for (int i=1;i<=n;i++){
if (S[i]) lx[i]-=a;
if (T[i]) ly[i]+=a;
}
}
void KM()
{
int i,j;
for (i=1;i<=n;i++){
lefts[i]=lx[i]=ly[i]=0;
for (j=1;j<=n;j++){
lx[i]=max(lx[i],w[i][j]);
}
}
for (i=1;i<=n;i++){
for (;;){
memset(S,0,sizeof S);
memset(T,0,sizeof T);
if (dfs(i)) break;
else update();
}
}
}
int main()
{
while (scanf("%d",&n)!=EOF)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) scanf("%d",&w[i][j]);
memset(lefts,-1,sizeof lefts);
KM();
int ans=0;
for (int i=1;i<=n;i++){
ans+=lx[i];
ans+=ly[i];
}
printf("%d\n",ans);
}
return 0;
}

HDU_2255 二分图最佳完美匹配 KM匈牙利算法,布布扣,bubuko.com

时间: 06-04

HDU_2255 二分图最佳完美匹配 KM匈牙利算法的相关文章

(转)二分图的最大匹配、完美匹配和匈牙利算法

转载自http://www.renfei.org/blog/bipartite-matching.html 二分图的最大匹配.完美匹配和匈牙利算法 这篇文章讲无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)和完美匹配(perfect matching),以及用于求解匹配的匈牙利算法(Hungarian Algorithm):不讲带权二分图的最佳匹配. 二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是

二分图的最大匹配、完美匹配和匈牙利算法(转)

转载自:http://blog.csdn.net/pi9nc/article/details/11848327 二分图的最大匹配.完美匹配和匈牙利算法 这篇文章讲无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)和完美匹配(perfect matching),以及用于求解匹配的匈牙利算法(Hungarian Algorithm):不讲带权二分图的最佳匹配. 二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这

二分图的最大匹配、完美匹配和匈牙利算法

这篇文章讲无权二分图(unweighted bipartite graph)的最大匹配(maximum matching)和完美匹配(perfect matching),以及用于求解匹配的匈牙利算法(Hungarian Algorithm):不讲带权二分图的最佳匹配. 二分图:简单来说,假设图中点能够被分为两组.而且使得全部边都跨越组的边界,则这就是一个二分图.准确地说:把一个图的顶点划分为两个不相交集 U和V .使得每一条边都分别连接U.V中的顶点. 假设存在这种划分,则此图为一个二分图.二分

UVALive 4043 Ants 蚂蚁(二分图最佳完美匹配)

题意:n个蚂蚁n棵树,蚂蚁与树要配对,在配对成功的一对之间连一条线段,要求所有线段不能相交.按顺序输出蚂蚁所匹配的树. 思路:这个题目真是技巧啊,如果知道要求的就是整体最优,那么就容易做了.而不能用贪心来为每个蚂蚁选择最近的树,这样可能八成还是相交了. 整体最优能让每条线段不相交,证明: 假设a1-b1与a2-b2相交.则dis(a1,b1)+dis(a2,b2)>=dis(a1,b2)+dis(a2,b1).如果我们所决定的最优匹配是按照整体距离最短来匹配的,那么dis(a1,b1)+dis(

hdu 3605 Escape 二分图的多重匹配(匈牙利算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3605 Escape Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 8001    Accepted Submission(s): 1758 Problem Description 2012 If this is the end of th

UVALive 4043 转化最佳完美匹配

首先黑点和白点是组成一个二分图这毫无疑问 关键是题目中要求的所有黑白配的线不能交叉...一开始我也没想到这个怎么转化为二分图里面的算法. 后来看书才知道,如果两两交叉,则可以把两根线当四边形的对角线,连四边形的两条边,则肯定不交叉,而且一个很明显的特征是,不交叉的两条线的他们的长度和 一定比交叉线的长度和小. 于是我们只要求出最小长度的线,就必定是不相交的.那就要用到最佳完美匹配了,首先算出两两点的欧几里得距离,然后取负数,这样走一遍匹配,得到的必定是最短的欧几里得距离,即不相交的线 #incl

HDU 2063:过山车(二分匹配,匈牙利算法)

过山车 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 9745    Accepted Submission(s): 4294 Problem Description RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了.可是,过山车的每一排只有两个座位,而且还有条不成文的规矩,就是每个女生必须找个个男生做par

HDU 1150:Machine Schedule(二分匹配,匈牙利算法)

Machine Schedule Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5371    Accepted Submission(s): 2658 Problem Description As we all know, machine scheduling is a very classical problem in compu

POJ 3014:Asteroids(二分匹配,匈牙利算法)

Asteroids Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 14399   Accepted: 7836 Description Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K as