hdu 2426 Interesting Housing Problem (二分图最佳匹配，km算法)

2016-06-01 · 2 min read · KM 二分图最佳匹配

hdu 2426 题目链接

题意：n个学生，m个宿舍，每个学生住一个宿舍，然后n个学生给若干个宿舍打分，分数可正可0可负，学生不能住打的分为负的宿舍，或者没有打分的宿舍。问在满足上述条件的前提下，所有学生住的宿舍的分数之和最大是多少。如果无解输出-1.

思路：二分图最佳匹配。。。读漏题QAQ. 原来分数为负的房间是不能住的啊。。。。

考虑无解的情况，如果学生数比宿舍数多，无解。

如果一个学生不喜欢任何宿舍或者没给任何宿舍打分，无解。

然后KM.

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年06月01日 星期三 19时35分04秒
  4File Name :code/hdu/2426.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=505;
 34int n,m,e;
 35int w[N][N];
 36int link[N];
 37int lx[N],ly[N];
 38bool visx[N],visy[N];
 39int slk[N];
 40
 41void init()
 42{
 43    ms(w,0xc0);
 44}
 45
 46
 47bool find( int u)
 48{
 49    visx[u] = true;
 50
 51    for ( int v = 1 ; v <= m ; v++)
 52    {
 53	if (visy[v]) continue;
 54	int tmp = lx[u] + ly[v] - w[u][v];
 55	if (tmp==0)
 56	{
 57	    visy[v] = true;
 58	    if (link[v]==-1||find(link[v]))
 59	    {
 60		link[v] = u ;
 61		return true;
 62	    }
 63	}else if (tmp<slk[v]) slk[v] = tmp;
 64    }
 65    return false;
 66}
 67int KM()
 68{
 69    ms(lx,0xc0);
 70    ms(ly,0);
 71    ms(link,-1);
 72
 73    for ( int i = 1 ; i <= n ; i++)
 74	for ( int j = 1 ; j <= m ; j++)
 75	    lx[i] = max(lx[i],w[i][j]);
 76
 77    for ( int i = 1 ; i <= n ; i++) if (lx[i]==-inf-1) return -1; 
 78
 79    for ( int i = 1 ; i <= n ; i++)
 80    {
 81	ms(slk,0x3f);
 82
 83	while (true)
 84	{
 85	    ms(visx,false);
 86	    ms(visy,false);
 87
 88	    if (find(i)) break;
 89
 90	    int d = inf;
 91
 92	    for ( int j = 1 ; j <= m ; j++)
 93		if (!visy[j]&&slk[j]<d) d = slk[j];
 94	   // cout<<"d:"<<d<<endl;
 95
 96	    for ( int j = 1 ; j <= n ; j++)
 97		if (visx[j]) lx[j]-=d;
 98	    for ( int j = 1 ;j  <= m ; j++)
 99		if (visy[j]) ly[j]+=d; else slk[j]-=d;
100
101	}
102    }
103
104    int res = 0 ;
105    for ( int i = 1 ; i <= m ; i++)
106	if (link[i]>-1) res += w[link[i]][i];
107
108 //   if (res<-5E8) res = -1;
109    return res;
110}
111int main()
112{
113	#ifndef  ONLINE_JUDGE 
114	freopen("code/in.txt","r",stdin);
115  #endif
116	int cas = 0 ;
117	while (scanf("%d%d%d",&n,&m,&e)!=EOF)
118	{
119
120	    init();
121	    for ( int i = 1 ; i <= e ; i++)
122	    {
123		int u,v,cost;
124		scanf("%d%d%d",&u,&v,&cost);
125		u++;
126		v++;
127		if (cost<0) continue;//? mdzz，读漏了。。喜欢程度为负是不能住的。
128		w[u][v] = cost;
129	    }
130
131	    printf("Case %d: ",++cas);
132	    if (n>m)  //学生比房间数多。
133	    {
134		puts("-1");
135		continue;
136	    }
137
138	    int ans = KM();
139	    printf("%d\n",ans);
140	}
141
142  #ifndef ONLINE_JUDGE  
143  fclose(stdin);
144  #endif
145    return 0;
146}