hdu 2255 奔小康赚大钱 (二分图最优匹配，KM算法)

时间：2023-01-16 06:28:08

Description

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

Input

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

Output

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

 

Sample Input

    
    
    

     
     
     2
100 10
15 23
 

Sample Output

    
    
    

     
     
     123
    
    
    

    
    
    

     
     
      
    
    
    

    
    
    

     
     
      
    
    
    

    
    
    

     
     
     最优匹配：使二分图的边权和最大的完备匹配。（如果二分图的两个点集不相等可以通过加“点” 和“权值为0的边”实现转化）
    
    
    

    
    
    

     
     
     可行顶标：若L(x)是顶点x对应的顶标值。可行顶标对于图中的每条边(x,y)都有L(x)+L(y)>=w(x,y) 相等子图：只包含L(x)+L(y)=w(x,y)的边的子图
    
    
    

    
    
    

     
     
      
    
    
    

    
    
    

     
     
     算法流程
    
    
    

    
    
    

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

    
    
    

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

    
    
    

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

    
    
    

     
     
      
    
    
    

    
    
    

     
     
     修改顶标的方法：当从 Xi 开始寻找交错路失败后，得到一棵交错树，对交错树中 X 顶点的顶标减少 d 值， Y 顶点的顶标增加 d 值。 对于图中所有的边 (i,j) 有：
    
    
    

    
    
    

     
     
      1）i和j都不在交错树中，边(i,j)仍然不属于相等子图  2）i和j都在交错树中，边(i,j)仍然属于相等子图 3）i不在交错树中，j在交错树中，a[i]+b[j]扩大，边(i,j)不属于相等子图 4）i在交错树,j不在交错树中,边(i,j)有可能加入到相等子图中
    
    
    

    
    
    

     
     
      
    
    
    

    
    
    

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

    
    
    

     
     
      
    
    
    

    
    
    

     
     
     由于在算法过程一直保持顶标的可行性，所以任意一个匹配的权值和肯定小于等于所有结点的顶标之和，又因为在扩大相等子图过程中优先加入了权值最大边，所以在相等子图中找到的第一个完备匹配就是最优匹配。
    
    
    
 
 
KM算法流程:
1.对二分图的两部分顶点初始化
2.KM算法用匈牙利算法寻找完备匹配
3.如果未找到就修改相应顶点值
4.重复（2）(3)直到找到相等子图的完备匹配为止；
 
 
#include <stdio.h>
#include <string.h>
#define INF 99999999
int N,temp; //temp记录每次顶标需要变化的修改量
int map[310][310],matchy[310];   //数组 map 记录边权值,数组 matchy 记录顶点 y 的匹配
int lx[310],ly[310]; //数组 lx 和 ly 分别记录顶点 x 和 y 的顶标值
int visitx[310],visity[310]; //数组 visitx 和 visity 分别记录顶点 x 和 y 是否被访问
int findpath(int x) //寻找最优解，匈牙利算法
{
    int i,t;
    visitx[x]=1;
    for(i=1;i<=N;i++)
    {
        if(visity[i])
            continue;
        t=lx[x]+ly[i]-map[x][i];
        if(t==0)   //说明是相等子图
        {
            visity[i]=1;
            if(matchy[i]==-1||findpath(matchy[i]))
            {
                matchy[i]=x;
                return 1;
            }
        }
        else if(temp>t)  //不在相等子图
            temp=t;
    }
    return 0;
}
void KM()
{
    int i,j,sum=0;
    for(i=1;i<=N;i++)   //对n个点匹配
    {
        while(1)
        {
            memset(visitx,0,sizeof(visitx));
            memset(visity,0,sizeof(visity));
            temp=INF;
            if(findpath(i))  //匹配成功
                break;
            for(j=1;j<=N;j++)  //匹配失败，找最小值 ，更新顶标
            {
                if(visitx[j])
                    lx[j]=lx[j]-temp;
                if(visity[j])
                    ly[j]=ly[j]+temp;
            }
        }
    }
}
int main()
{
    int i,j,sum=0;
    while(scanf("%d",&N)!=EOF)
    {
        memset(map,0,sizeof(map));
        memset(lx,0,sizeof(lx));
        memset(ly,0,sizeof(ly));
        memset(matchy,-1,sizeof(matchy));
        for(i=1;i<=N;i++)
           for(j=1;j<=N;j++)
           {
              scanf("%d",&map[i][j]);
              if(lx[i]<map[i][j])  //lx[i]为权值最大的边 ，ly[i]为0
                lx[i]=map[i][j];
           }
        KM();
        sum=0;    //权值相加
        for(i=1;i<=N;i++)
          sum=sum+map[matchy[i]][i];
        printf("%d\n",sum);
    }
    return 0;
}
标签：

相关文章