[KM算法]hdoj 2426：Interesting Housing Problem

大致题意：

    有n个小孩要去m间屋子，每间屋子只能住一个人。每个小孩都会对一些屋子打分。已知每个小孩不能去那些他打负分和没打分的屋子，求安排住宿后所有人对自己屋子打分之和最大值是多少。

 

大致思路：

    KM二分图最大权匹配。在KM模板里面加一步检验是否所有的n都有匹配。很不清楚为什么加了一步，n>m就直接输出-1，却wa了，去掉之后ac了。求大牛解释。

 

#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=505;
const int inf=1<<30;
int map[nMax][nMax];
int lx[nMax],ly[nMax];
int mapch[nMax];
int stack[nMax];
bool sy[nMax],sx[nMax];
int n,m,e;
int find (int u){
    int v,t;
    sx[u]=1;
    for(v=1;v<=m;v++){
        if(sy[v]) continue;
        t=lx[u]+ly[v]-map[u][v];
        if(t==0){
            sy[v]=1;
            if(mapch[v]==-1||find(mapch[v])){
                mapch[v]=u;
                return 1;
            }
        }
        else if(t<stack[v]) stack[v]=t;
    }
    return 0;
}
int KM(){
    int i,j,k,d,cnt=0,sum=0;
    for(i=1;i<=m;i++)
        ly[i]=0;
    memset(mapch,-1,sizeof(mapch));
    for(i=1;i<=n;i++){
        lx[i]=-inf;
        for(j=1;j<=m;j++)
            if(map[i][j]>lx[i])
                lx[i]=map[i][j];
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            stack[j]=inf;
        while(1){
            for(k=1;k<=m;k++) sy[k]=0;
            for(k=1;k<=n;k++) sx[k]=0;
            if(find(i)) break;
            d=inf;
            for(k=1;k<=m;k++)
                if(!sy[k]&&stack[k]<d)
                    d=stack[k];
            for(k=1;k<=n;k++)
                if(sx[k]) lx[k]-=d;
            for(k=1;k<=m;k++)
                if(sy[k]) ly[k]+=d;
                else stack[k]-=d;
        }
    }
    for(i=1;i<=m;i++)
        if(mapch[i]!=-1&&map[mapch[i]][i]!=-inf){
            sum+=map[mapch[i]][i];
            cnt++;
        }
    if(cnt==n) return sum;//判断是否能完成n的最佳匹配
    else return -1;
}

int main(){
    int i,j,k,a,b,c,ans,cas=0;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        cas++;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                map[i][j]=-inf;
        while(k--){
            scanf("%d%d%d",&a,&b,&c);
            a++,b++;
            if(c>=0){
                map[a][b]=c;
            }
        }
        printf("Case %d: ",cas);
//        if(a>b){
//            printf("-1\n");
//            continue;
//        }
        ans=KM();
        printf("%d\n",ans);
    }
    return 0;
}