hdu2255 奔小康赚大钱,最大权匹配,KM算法

点击打开链接

最大权匹配

KM算法

算法步骤:

设顶点Xi的顶标为a[i],顶点Yi的顶标为b[i]

ⅰ.初始时,a[i]为与Xi相关联的边的最大权值,b[j]=0,保证a[i]+b[j]>=w(i,j)成立

ⅱ.当相等子图中不包含完备匹配时,就适当修改顶标以扩大相等子图,直到找到完备匹配为止

ⅲ.修改顶标的方法

当从Xi寻找交错路失败后,得到一棵交错树,它的所有叶子节点都是X节点,对交错树中X顶点的顶标减少d值,Y顶点的顶标增加d值,对于图中所有的边(i,j),

可以看到:

i和j都不在交错树中,边(i,j)仍然不属于相等子图

i和j都在交错树中,边(i,j)仍然属于相等子图

i不在交错树中,j在交错树中,a[i]+b[j]扩大,边(i,j)不属于相等子图

i在交错树,j不在交错树中,边(i,j)有可能加入到相等子图中

为了使a[i]+b[j]>=w(i,j)始终成立,且至少有一条边加入到相等子图中,d=min{a[i]+b[j]-w(i,j)},i在交错树中,j不在交错树中

时间复杂度:需要找O(n)次增广路,每次增广最多需要修改O(n)次顶标,每次修改顶标时枚举边来求d值,复杂度为O(n2),总的复杂度为O(n4).简单优化可以降低到O(n3),每个Y顶点一个“松弛量”函数slack,每次开始找增广路时初始化为无穷大。在寻找增广路的过程中,检查边(i,j)时,如果不在相等子图中,则让slack[j]变成原值与A[i]+B[j]-w[i,j]的较小值。这样,在修改顶标时,取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点:修改顶标后,要把所有的slack值都减去d。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#define for0(a,b) for(a=0;a<b;++a)
#define for1(a,b) for(a=1;a<=b;++a)
#define foru(i,a,b) for(i=a;i<=b;++i)
#define ford(i,a,b) for(i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const int maxn = 310;
const int INF = 1e9;
/*KM算法
 *O(nx*nx*ny)
 *求最大权匹配
 *若求最小权匹配,可将权值取相反数,结果再取相反数。
 */
int nx, ny;
int g[maxn][maxn];
int linker[maxn], lx[maxn], ly[maxn];//y中各点匹配状态,x,y中的顶标
int slack[maxn];
bool visx[maxn], visy[maxn];

bool DFS(int x)
{
    visx[x] = true;
    for(int y=0; y<ny; ++y){
        if(visy[y]) continue;
        int tmp = lx[x] + ly[y] - g[x][y];
        if(tmp == 0){
            visy[y] = true;
            if(linker[y] == -1 || DFS(linker[y])){
                linker[y] = x;
                return true;
            }
        }
        else if(slack[y]> tmp)
            slack[y] = tmp;
    }
    return false;
}

int KM()
{
    memset(linker, -1, sizeof linker );
    memset(ly, 0, sizeof ly );
    for(int i=0; i<nx; ++i){
        lx[i] = - INF;
        for(int j=0; j<ny; ++j)
            if(g[i][j]> lx[i])
                lx[i] = g[i][j];
    }
    for(int x=0; x<nx; ++x)
    {
        for(int i=0; i<ny; ++i)
            slack[i] = INF;
        while(true)
        {
            memset(visx, false, sizeof visx );
            memset(visy, false, sizeof visy );
            if(DFS(x)) break;
            int d = INF;
            for(int i=0; i<ny; ++i)
                if(!visy[i] && d>slack[i])
                    d = slack[i];
            for(int i=0; i<nx; ++i)
                if(visx[i])
                    lx[i] -= d;
            for(int i=0; i<ny; ++i)
            {
                if(visy[i]) ly[i] += d;
                else slack[i] -= d;
            }
        }
    }
    int res = 0;
    for(int i=0; i<ny; ++i)
        if(linker[i] != -1)
            res += g[linker[i]][i];
    return res;
}

//HDU 2255
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.cpp","r",stdin);
    freopen("out.cpp", "w", stdout);
#endif // ONLINE_JUDGE
    int n;
    while(~scanf("%d", &n))
    {
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                scanf("%d", &g[i][j]);
        nx = ny = n;
        printf("%d\n" ,KM());
    }
    return 0;
}
时间: 10-02

hdu2255 奔小康赚大钱,最大权匹配,KM算法的相关文章

hdu2255 奔小康赚大钱 二分图最佳匹配--KM算法

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

HDU2255 奔小康赚大钱【二分图最佳匹配】

题目链接: http://acm.hdu.edu.cn/showproblem.php? pid=2255 题目大意: 村里要分房子. 有N家老百姓,刚好有N间房子.考虑到每家都要有房住,每家必须分配到一间房子且 仅仅能分配到一间房子.另外, 村长为了得到最大利益,让老百姓对房子进行估价. 比方有3件房子,一 家老百姓能够对第一间出10万,对第二间出2万,对第三间出4万.第二家老百姓能够对第一间出8万, 对第二家出3万,对第三间出5万.那么问题来了:怎么分配,才干使利益最大化. (村民房子不一定

HDU 2255 奔小康赚大钱(二分匹配之KM算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2255 Problem Description 传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子. 这可是一件大事,关系到人民的住房问题啊.村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子. 另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓

奔小康赚大钱(km)

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

奔小康赚大钱 hdu 2255

奔小康赚大钱 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4211    Accepted Submission(s): 1825 Problem Description 传说在遥远的地方有一个很富裕的村落,有一天,村长决定进行制度改革:又一次分配房子. 这但是一件大事,关系到人民的住房问题啊.村里共同拥有n间房间,刚好有n家老百姓

HDU 2255 ——奔小康赚大钱——————【KM算法裸题】

奔小康赚大钱 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 2255 Description 传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子. 这可是一件大事,关系到人民的住房问题啊.村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到

hdu 2255 奔小康赚大钱(KM算法)

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

HDU 2255 奔小康赚大钱(KM算法求完备匹配)

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

HDU 2255 奔小康赚大钱 KM算法的简单解释

KM算法一般用来寻找二分图的最优匹配. 步骤: 1.初始化可行标杆 2.对新加入的点用匈牙利算法进行判断 3.若无法加入新编,修改可行标杆 4.重复2.3操作直到找到相等子图的完全匹配. 各步骤简述: 1.根据二分图建立2个可行标杆; lx为x的可行标杆,初始化lx[i]为与i点相连的最大边 ly为y的可行标杆,初始化为0. 可行性的判断条件应为lx[x]+ly[y] >= Map[x][y]. 2.对于新加入的点用匈牙利算法经行判断,确定改点能否加入旧子图中,形成新子图. 对于该加入的点有两种