hdu 2426 Interesting Housing Problem(KM)

hdu 2426 Interesting Housing Problem(KM)

题目：​​Housing Problem

Time Limit: 10000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2725    Accepted Submission(s): 985

Problem Description

For any school, it is hard to find a feasible accommodation plan with every student assigned to a suitable apartment while keeping everyone happy, let alone an optimal one. Recently the president of University ABC, Peterson, is facing a similar problem. While Peterson does not like the idea of delegating the task directly to the class advisors as so many other schools are doing, he still wants to design a creative plan such that no student is assigned to a room he/she dislikes, and the overall quality of the plan should be maximized. Nevertheless, Peterson does not know how this task could be accomplished, so he asks you to solve this so-called "interesting" problem for him. Suppose that there are N students and M rooms. Each student is asked to rate some rooms (not necessarily all M rooms) by stating how he/she likes the room. The rating can be represented as an integer, positive value meaning that the student consider the room to be of good quality, zero indicating neutral, or negative implying that the student does not like living in the room. Note that you can never assign a student to a room which he/she has not rated, as the absence of rating indicates that the student cannot live in the room for other reasons. With limited information available, you've decided to simply find an assignment such that every student is assigned to a room he/she has rated, no two students are assigned to the same room, and the sum of rating is maximized while satisfying Peterson's requirement. The question is … what exactly is the answer?

Input

There are multiple test cases in the input file. Each test case begins with three integers, N, M, and E (1 <= N <= 500, 0 <= M <= 500, 0 <= E <= min(N * M, 50000)), followed by E lines, each line containing three numbers, S i, R i, V i, (0 <= S i < N, 0 <= R i < M, |V i| <= 10000), describing the rating V i given by student S i for room R i. It is guaranteed that each student will rate each room at most once. Each case is followed by one blank line. Input ends with End-of-File.

Output

For each test case, please output one integer, the requested value, on a single line, or -1 if no solution could be found. Use the format as indicated in the sample output.

Sample Input

3 5 5 0 1 5 0 2 7 1 1 6 1 2 3 2 4 5 1 1 1 0 0 0 1 1 0

Sample Output

Case 1: 18 Case 2: 0 Case 3: -1

Source

​​2008 Asia Hangzhou Regional Contest Online ​​

分析：要求完美匹配下的最大分数。所以必须匹配人数和总的人数相等才行，否则输出-1，最大分数的话使用KM算法，要求最大分数，让同学们满意所以负数分数干脆不输入。另外如果n>m的话，KM会进入死循环，所以要处理一下。

#include #include #include using namespace std;const int M=510,inf=0x3f3f3f3f;typedef long long LL;LL nx,ny;LL link[M],lx[M],ly[M],slack[M];//lx,ly为顶标，nx,ny分别为x点集y点集的个数LL visx[M],visy[M],w[M][M];int useroom=0;LL DFS(LL x){ visx[x] = 1; for (LL y = 1; y <= ny; y ++) { if (visy[y] || w[x][y]<0) continue; //w[x][y]<0 don't match LL t = lx[x] + ly[y] - w[x][y]; if (t == 0) { visy[y] = 1; if (link[y] == -1||DFS(link[y])) { link[y] = x; // if not find, it's TLE return 1; } } else if (slack[y] > t) //不在相等子图中slack 取最小的 slack[y] = t; } return 0;}LL KM(){ LL i,j; memset (link,-1,sizeof(link)); memset (ly,0,sizeof(ly)); memset(lx,-1,sizeof(lx)); //lx初始化为与它关联边中最大的 for (i = 1; i <= nx; i ++) for (j = 1; j <= ny; j ++) if (w[i][j] > lx[i]) lx[i] = w[i][j]; for (LL x = 1; x <= nx; x ++) { for (i = 1; i <= ny; i ++) slack[i] = inf; while (1) { memset (visx,0,sizeof(visx)); memset (visy,0,sizeof(visy)); if (DFS(x)) break; LL d = inf; for (i = 1; i <= ny; i ++) if (!visy[i]&&d > slack[i]) d = slack[i]; for (i = 1; i <= nx; i ++) if (visx[i]) lx[i] -= d; for (i = 1; i <= ny; i ++) if (visy[i]) ly[i] += d; else slack[i] -= d; } } LL res = 0,cnt=0; for (i = 1; i <= ny; i ++) if (link[i] > -1){ res += w[link[i]][i]; cnt++; } if(cnt!=nx) res=-1; //非完美匹配 return res;}bool room[M];int main(){ //freopen("cin.txt","r",stdin); LL ca=1,n,m,e; while(cin>>n>>m>>e){ memset(w,-1,sizeof(w)); nx=n,ny=m; LL ans; LL s,r,v; for(LL i=0;im || e==0){ ans=-1; goto loop; } ans=KM();loop: printf("Case %lld: %lld\n",ca++,ans); } return 0;}/*死循环例子：1 0 10 0 1*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。