2014
01-26

# Interesting Housing Problem

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?

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, Si, Ri, Vi, (0 <= Si < N, 0 <= Ri < M, |Vi| <= 10000), describing the rating Vi given by student Si for room Ri. 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.

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, Si, Ri, Vi, (0 <= Si < N, 0 <= Ri < M, |Vi| <= 10000), describing the rating Vi given by student Si for room Ri. 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.

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

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

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
using namespace std;
#define N 501
#define INF 0x3fffffff

struct node
{
int to,next;
int w;
}edge[50001];

int cnt,pre[N];
int n,m,e;
int frt[N];
int wx[N],wy[N];
int save[N];
int markx[N],marky[N];

{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=pre[u];
pre[u] = cnt++;
}

int dfs(int s)
{
markx[s]=1;
for(int p=pre[s];p!=-1;p=edge[p].next)
{
int v=edge[p].to;
if( wx[s]+wy[v]-edge[p].w < save[v]) save[v]=wx[s]+wy[v]-edge[p].w;
if(marky[v]==1||wx[s]+wy[v]!=edge[p].w) continue;
marky[v]=1;
if(frt[v]==-1 || dfs(frt[v])==1)
{
frt[v]=s;
return 1;
}
}
return 0;
}

int KM()
{
memset(frt,-1,sizeof(frt));
memset(wx,0,sizeof(wx));
memset(wy,0,sizeof(wy));
for(int i=1;i<=n;i++)
for(int p=pre[i];p!=-1;p=edge[p].next)
wx[i]=max(wx[i],edge[p].w);
for(int i=1;i<=n;i++)
{
while(1)
{
memset(markx,0,sizeof(markx));
memset(marky,0,sizeof(marky));
for(int j=1;j<=m;j++)
save[j]=INF;
if( dfs(i) == 1 ) break;
int mi=INF;
for(int j=1;j<=m;j++)
if(marky[j]==0 && save[j]<mi) mi = save[j];
if(mi==INF) return -1;
for(int j=1;j<=n;j++)
if(markx[j]==1) wx[j]-=mi;
for(int j=1;j<=m;j++)
if(marky[j]==1) wy[j]+=mi;
}
}
int sum=0;
for(int i=1;i<=n;i++)
for(int p=pre[i];p!=-1;p=edge[p].next)
if(frt[edge[p].to]==i) sum+=edge[p].w;
return sum;
}

int main()
{
int tt=1;
while(scanf("%d%d%d",&n,&m,&e)!=EOF)
{
cnt=0;
memset(pre,-1,sizeof(pre));
for(int i=0;i<e;i++)
{
int x,y;
int key;
scanf("%d%d%d",&x,&y,&key);
x++; y++;
if(key>=0)
{
}
}
printf("Case %d: ",tt++);
if(n>m) printf("-1\n");
else
printf("%d\n",KM());
}
return 0;
}

1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

3. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。