首页 > 搜索 > DFS搜索 > hdu 2426 Interesting Housing Problem-DFS-[解题报告]C++
2014
01-26

hdu 2426 Interesting Housing Problem-DFS-[解题报告]C++

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];


void add_edge(int u,int v,int w)
{
    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)
            {
                add_edge(x,y,key);
            }
        }
        printf("Case %d: ",tt++);
        if(n>m) printf("-1\n");
        else
            printf("%d\n",KM());
    }
    return 0;
}

解题转自:http://www.cnblogs.com/chenhuan001/archive/2013/05/07/3066002.html


,
  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作为参数。