HDU 2426 Interesting Housing Problem (最大权完美匹配)【KM】

题目大意：

学校里有n个学生和m个公寓房间，每个学生对一些房间有一些打分，如果分数为正，说明学生喜欢这个房间，若为0，对这个房间保持中立，若为负，则不喜欢这个房间。学生不会住进不喜欢的房间和没有打分的房间。问安排这n个学生来求最大的分数，如果不能够使这些学生全部入住房间，就输出-1，每个房间最多只能住一个学生。

解题分析：

因为需要求带权二分图，所以用KM算法，需要注意的是，边权为负的两点不能进行匹配，并且，最后需要判断是否符合题意，即是否所有学生都有房间。

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int N = ;

 #define INF 0x3f3f3f3f

 #define CLR(a,b) memset(a,b,sizeof(a))

 #define rep(i,s,t) for(int i=s;i<t;i++)

 int nx,ny,k;

 int w[N][N],linker[N],visx[N],visy[N],lx[N],ly[N],slack[N];

 bool DFS(int x){

     visx[x]=;

     rep(y,,ny){

         if(!visy[y]&&w[x][y]>=){    //如果w[x][y]<0，就不能匹配

             int tmp=lx[x]+ly[y]-w[x][y];

             if(tmp==){

                 visy[y]=;

                 if(linker[y]==-||DFS(linker[y])){

                     linker[y]=x;

                     return true;

                 }

             }else slack[y]=min(slack[y],tmp);

         }

     }

     return false;

 }

 int KM(){

     CLR(linker,-);CLR(ly,);

     rep(i,,nx){

         lx[i]=-INF;

         rep(j,,ny){

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

         }

         if(lx[i]<)return -;    //在取完最值后,lx[i]仍然<0,说明该人不想住进任何一间房子，所以直接返回-1即可

     }

     rep(x,,nx){

         rep(i,,ny)slack[i]=INF;

         while(true){

             CLR(visx,);CLR(visy,);

             if(DFS(x))break;

             int d=INF;

             rep(i,,ny)if(!visy[i])d=min(d,slack[i]);

             rep(i,,nx)if(visx[i])lx[i]-=d;

             rep(i,,ny)

                 if(visy[i])ly[i]+=d;

                 else slack[i]-=d;

         }

     }

     int res=,count=;

     rep(y,,ny){

         if(linker[y]!=-)res+=w[linker[y]][y],count++;    //count记录有房子住的人数

     }

     if(count<nx)return -;

     return res;

 }

 int main(){

     int ncase=;

     while(~scanf("%d%d%d",&nx,&ny,&k)){

         CLR(w,-);

         rep(i,,k){

             int a,b,c;scanf("%d%d%d",&a,&b,&c);

             w[a][b]=c;

         }

         printf("Case %d: %d\n",++ncase,KM());

     }

 }

2018-11-18

巴特西

HDU 2426 Interesting Housing Problem (最大权完美匹配)【KM】

最新文章

热门文章