hdu2255 二分图最大权配KM

KM算法:
hdu2255 (大概理解了参考博客: http://blog.csdn.net/niushuai666/article/details/7171880)
         所谓交错树：就是已经匹配好的。(我自己理解的)
         交错树中的X集合和不在交错树中的Y集合去找：d=min(lx[i]-map[i][j]); 然后交错树中的x顶点-d，交错树中的Y顶点+d；
         其实核心还是逐步找最优解的过程。
         还有一个知识点：

　　　　Tutte定理：一个图G有完备匹配，其充要条件是，对于图中任意点集U，去掉U后剩下的具有奇数个顶点的连通分量个数（记作o(G-U)）不超过U中的顶点数。。
         若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图（概念很重要））有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
                 (理解性记忆的，我现在也就能理解到这个水平了)
                 还有kuangbin大哥写的KM博客: http://www.cnblogs.com/kuangbin/archive/2012/08/19/2646535.html

　　　　　　 hdu2255 题解：http://blog.csdn.net/niushuai666/article/details/7171525

Problem Description

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

Input

输入数据包含多组测试用例，每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量)，接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。

Output

请对每组数据输出最大的收入值，每组的输出占一行。

Sample Input

100 10

15 23

Sample Output

123

AC代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

#define INF 0xfffffff

int map[][];

int x[],y[];

int vx[],vy[];

int p[];

int n;

int Find(int A)

{

    vx[A]=;

    for(int i=; i<=n; i++)

    {

        if(!vy[i] && map[A][i]==x[A]+y[i])

        {

            vy[i]=;

            if(p[i]==- || Find(p[i]))

            {

                p[i]=A;

                return ;

            }

        }

    }

    return ;

}

void KM()

{

    memset(x,,sizeof(x));

    memset(y,,sizeof(y));

    for(int i=; i<=n; i++)

        for(int j=; j<=n; j++)

            x[i]=max(x[i],map[i][j]);

    for(int i=; i<=n; i++)

    {

        while()

        {

            memset(vx,,sizeof(vx));

            memset(vy,,sizeof(vy));

            if(Find(i))

                break;

            else

            {

                int m=INF;

                for(int j=; j<=n; j++)

                    if(vx[j])

                        for(int k=; k<=n; k++)

                            if(!vy[k] && m>x[j]+y[k]-map[j][k])

                                m=x[j]+y[k]-map[j][k];

                for(int j=; j<=n; j++)

                {

                    if(vx[j]) x[j]-=m;

                    if(vy[j]) y[j]+=m;

                }

            }

        }

    }

}

int main()

{

    while(scanf("%d",&n)==)

    {

        for(int i=; i<=n; i++)

            for(int j=; j<=n; j++)

                scanf("%d",&map[i][j]);

        int ans=;

        memset(p,-,sizeof(p));

        KM();

        for(int i=; i<=n; i++)

            ans+=map[p[i]][i];

        printf("%d\n",ans);

    }

    return ;

}

KM标码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<climits>

#include<algorithm>

using namespace std;

#define N 310

int map[N][N];

bool visitx[N], visity[N];

int lx[N],ly[N];

int match[N];

int n;

bool Hungary(int u) //匈牙利算法

{

    visitx[u]=true;

    for(int i=; i<n; i++)

    {

        if(!visity[i] && lx[u]+ly[i]==map[u][i])

        {

            visity[i]=true;

            if(match[i]==- || Hungary(match[i]))

            {

                match[i]=u;

                return true;

            }

        }

    }

    return false;

}

void KM_perfect_match()

{

    int temp;

    memset(lx,,sizeof(lx)); //初始化顶标

    memset(ly,,sizeof(ly)); //ly[i]为0

    for(int i=; i<n; i++) //lx[i]为权值最大的边

        for(int j=; j<n; j++)

            lx[i]=max(lx[i],map[i][j]);

    for(int i = ; i < n; ++i) //对n个点匹配

    {

        while()

        {

            memset(visitx,false,sizeof(visitx));

            memset(visity,false,sizeof(visity));

            if(Hungary(i)) //匹配成功

                break;

            else //匹配失败，找最小值

            {

                temp=INT_MAX;

                for(int j=; j<n; j++) //x在交错树中

                    if(visitx[j])

                        for(int k=; k<n; ++k) //y在交错树外

                            if(!visity[k] && temp>lx[j]+ly[k]-map[j][k])

                                temp=lx[j]+ly[k]-map[j][k];

                for(int j=; j<n; j++) //更新顶标

                {

                    if(visitx[j]) lx[j]-=temp;

                    if(visity[j]) ly[j]+=temp;

                }

            }

        }

    }

}

int main()

{

    int ans;

    while(scanf("%d",&n)!=EOF)

    {

        ans=;

        memset(match,-,sizeof(match));

        for(int i=; i<n; i++)

            for(int j=; j<n; j++)

                scanf("%d",&map[i][j]);

        KM_perfect_match();

        for(int i=; i<n; i++) //权值相加

            ans+=map[match[i]][i];

        printf("%d\n",ans);

    }

    return ;

}

优化的KM：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<climits>

#include<algorithm>

using namespace std;

#define N 310

int map[N][N];

bool visitx[N], visity[N];

int lx[N],ly[N];

int slack[N];

int match[N];

int n;

int Scan()  //输入外挂

{

    int res=,ch;

    while(!((ch=getchar())>='' && ch<='' ) )

        if(ch==EOF)  return << ;

    res=ch-'';

    while((ch=getchar())>=''&&ch<='')

        res=res*+(ch-'') ;

    return res;

}

bool Hungary(int u) //匈牙利算法

{

    visitx[u]=true;

    for(int i=; i<n; i++)

    {

        if(visity[i])

            continue;

        if(lx[u]+ly[i]==map[u][i])

        {

            visity[i]=true;

            if(match[i]==-||Hungary(match[i]))

            {

                match[i]=u;

                return true;

            }

        }

        else //不在相等子图

            slack[i]=min(slack[i], lx[u] + ly[i] - map[u][i]);

    }

    return false;

}

void KM_perfect_match()

{

    int temp;

    memset(lx,,sizeof(lx)); //初始化顶标

    memset(ly,,sizeof(ly)); //ly[i]为0

    for(int i=; i<n; i++) //lx[i]为权值最大的边

        for(int j=; j<n; j++)

            lx[i]=max(lx[i],map[i][j]);

    for(int i=; i<n; i++) //对n个点匹配

    {

        for(int j=; j<n; j++)

            slack[j]=INT_MAX;

        while()

        {

            memset(visitx,false,sizeof(visitx));

            memset(visity,false,sizeof(visity));

            if(Hungary(i)) //匹配成功

                break;

            else //匹配失败，找最小值

            {

                temp=INT_MAX;

                for(int j=; j<n; ++j)

                    if(!visity[j])

                        if(temp>slack[j])

                            temp=slack[j];

                for(int j=; j<n; j++) //更新顶标

                {

                    if(visitx[j]) lx[j]-=temp;

                    if(visity[j]) ly[j]+=temp;

                    else slack[j]-=temp;

                }

            }

        }

    }

}

int main()

{

    int ans;

    while(scanf("%d",&n)!=EOF)

    {

        ans=;

        memset(match,-,sizeof(match));

        for(int i=; i<n; i++)

            for(int j=; j<n; j++)

                map[i][j]=Scan();

        KM_perfect_match();

        for(int i=; i<n; ++i) //权值相加

            ans+=map[match[i]][i];

        printf("%d\n",ans);

    }

    return ;

}

巴特西

hdu2255 二分图最大权配KM

最新文章

热门文章