hdu2426解题报告

题意：这里有N个学生，M个寝室，E个意愿，每个意愿占一行，包括S，R，V表示S学生对R房间的渴望为V，那么这里的V如果为0表示这个学生对R房间表示中立，不喜欢也不讨厌，如果V为负数，就是不喜欢，不能安排，而且这里如果没有列出S对R的意愿，那么就表示不愿意，那么问题是根据给出的数据，输出安排学生的最大意愿是多少，如果不能安排就输出-1,

分析：由于我刚刚接触KM算法，开始遇到这个题目就想不通，这里的负数怎么处理....最后发现自己想太多啦，其实我们一开始给所有的学生对所有的房间赋值为-1，那么再输入数据，在匈牙利算法匹配的过程中我们对于关系为负数的就不考虑匹配，(如果没有此学生对某房间的意愿，那就是-1，表示不愿意)，那么匹配完了之后最后求总的意愿和的时候用一个cnt就算匹配数，如果为学生人数，那么就是全部匹配完，如果不为学生人数，那么就是有的人匹配不了，那么返回-1；那么就是简单的模板啦

那么上马：

// 343MS 1220K #include<stdio.h>#include<string.h>#define MAX 501#define INF 1<<30-1int N,M,E;int map[MAX][MAX];int link[MAX],slar[MAX],lx[MAX],ly[MAX];bool visx[MAX],visy[MAX];bool dfs(int x){visx[x]=true;for(int y=0;y<M;y++){if(!visy[y] && map[x][y]>=0)//如果map[x][y]<0 那么我们就不用匹配...{int t=lx[x]+ly[y]-map[x][y];if(t==0){visy[y]=true;if(link[y]==-1 || dfs(link[y])){link[y]=x;return true;}}else slar[y] = slar[y] > t ? t:slar[y];}}return false;}int KM(){int i,j;if(E==0) return -1;memset(link,-1,sizeof(link));memset(lx,-1,sizeof(lx));//这里先赋值为-1，一旦后面查找最大lx[i]的时候还出现<0 那么意思就是有一个人他什么都不想住..直接返回-1memset(ly,0,sizeof(ly));for(i=0;i<N;i++){for(j=0;j<M;j++)lx[i]=lx[i]>map[i][j] ? lx[i]:map[i][j];if(lx[i]<0) return -1;}for(int x=0;x<N;x++){for(i=0;i<M;i++) slar[i]=INF;while(1){memset(visx,false,sizeof(visx));memset(visy,false,sizeof(visy));if(dfs(x)) break;int d=INF;for(i=0;i<M;i++)if(!visy[i]) d=d>slar[i] ? slar[i]:d;for(i=0;i<N;i++)if(visx[i]) lx[i]-=d;for(i=0;i<M;i++)if(visy[i]) ly[i]+=d;    else   slar[i]-=d;}}int ans=0,cnt=0;for(i=0;i<M;i++)//cnt用来检测是否匹配了N个...不然就是安排不了if(link[i]!=-1)ans+=map[link[i]][i],cnt++;if(cnt<N)ans=-1;return ans;}int main(){int i,j;int a,b,c;int cas=1;while(~scanf("%d%d%d",&N,&M,&E)){/*for(i=0;i<N;i++) //没必要这样for(j=0;j<M;j++)map[i][j]=-INF;*/memset(map,-1,sizeof(map));for(i=0;i<E;i++){scanf("%d%d%d",&a,&b,&c);//if(c<0) continue;map[a][b]=c;}printf("Case %d: %d\n",cas++,KM());}return 0;}