HDU2255-KM

朱雀 2022-07-10 11:29 168阅读 0赞

# 奔小康赚大钱 #

**Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 8258    Accepted Submission(s): 3665**

Problem 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

Source

[HDOJ 2008 Summer Exercise（4）- Buffet Dinner][HDOJ 2008 Summer Exercise_4_- Buffet Dinner]

**题目大意**：

**                 n个村名选n个房子，每个村名都有自己喜欢的房子并且有个好感值，问怎么安排才能使好感值和最大**

**题目思路**：

带权二分图，解决该类问题的算法主要是KM算法，也可以用费用流但时间复杂度更高

关于KM算法我推荐两个写的好的博客：

KM算法：[图文解说][Link 1]  ，[趣味解说][Link 2]

**AC代码**：

#include<cstring>
    #include<cstdio>
    #define min(x,y) (x<y?x:y)
    #define max(x,y) (x>y?x:y)
    #define abs(x)  ((x)<0?-(x):(x))
    const int maxn = 1e2+20;
    const int inf = 0x3f3f3f3f;
    
    class KM{
    public:
        int n,m,numh,numm;
        int ph[maxn][2],pm[maxn][2];
        int mp[maxn][maxn],slack[maxn],link[maxn],ex_l[maxn],ex_r[maxn];
        bool vis_l[maxn],vis_r[maxn];
    
        bool dfs(int u){
            vis_l[u]=true;
            for(int i=1;i<=n;i++){
                if(!vis_r[i]){
                    if(ex_l[u]+ex_r[i]==mp[u][i]){
                        vis_r[i]=true;
                        if(link[i]==-1||dfs(link[i])){
                            link[i]=u;
                            return true;
                        }
                    }else {
                        slack[i]=min(slack[i],ex_l[u]+ex_r[i]-mp[u][i]);
                    }
                }
            }
            return false;
        }
    
        int sove(){
            for(int i=1;i<=n;i++){
                memset(slack,0x3f,sizeof(slack));
                while(1){
                    memset(vis_l,false,sizeof(vis_l));
                    memset(vis_r,false,sizeof(vis_r));
                    if(dfs(i))break;
                    int d = inf;
                    for(int j=1;j<=n;j++){
                        if(!vis_r[j])d=min(d,slack[j]);
                    }
                    for(int j=1;j<=n;j++){
                        if(vis_l[j])ex_l[j]-=d;
                        if(vis_r[j])ex_r[j]+=d;
                        else slack[j]-=d;
                    }
                }
            }
            int res = 0;
            for(int i=1;i<=n;i++){
                if(link[i]!=-1){
                    res+=mp[link[i]][i];
                }
            }
            return res;
        }
    
        void star(){
            while(~scanf("%d%d",&n,&m),n+m){
                init();
                char str[maxn];
                for(int i=1;i<=n;i++){
                    scanf("%s",str+1);
                    for(int j=1;j<=m;j++){
                        if(str[j]=='H')ph[++numh][0]=i,ph[numh][1]=j;
                        if(str[j]=='m')pm[++numm][0]=i,pm[numm][1]=j;
                    }
                }
                n=numh;
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        int x = abs(pm[i][0]-ph[j][0])+abs(pm[i][1]-ph[j][1]);
                        mp[i][j]=-x;
                        ex_l[i]=max(ex_l[i],mp[i][j]);
                    }
                }
                printf("%d\n",-sove());
            }
        }
    
        void init(){
            memset(link,-1,sizeof(link));
            memset(ex_r,0,sizeof(ex_r));
            memset(ex_l,-0x3f,sizeof(ex_l));
            numh=numm=0;
        }
    
    }km;
    
    int main()
    {
        km.star();
        return 0;
    }

[HDOJ 2008 Summer Exercise_4_- Buffet Dinner]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDOJ+2008+Summer+Exercise%A3%A84%A3%A9-+Buffet+Dinner&source=1&searchmode=source
[Link 1]: http://blog.csdn.net/zxn0803/article/details/49999267
[Link 2]: http://www.cnblogs.com/wenruo/p/5264235.html