Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2575 Accepted Submission(s): 1135
Problem Description
传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子。 这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须分配到一间房子且只能得到一间房子。 另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).
Input
输入数据包含多组测试用例,每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量),接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。
Output
请对每组数据输出最大的收入值,每组的输出占一行。
Sample Input
2
100 10
15 23
Sample Output
123
Source
HDOJ 2008 Summer Exercise(4)- Buffet Dinner
开始使用的是分组背包,但是悲剧啦,啦啦啦,
无奈,只好用KM来做,结果很理想!....
分组背包超时,但是还是贴上代码ba!...
代码:
1 /*@code龚细军*/
2 #include<stdio.h>
3 #include<string.h>
4 #define maxn 301
5 int peo[maxn][maxn];
6 int dp[maxn];
7
8 int max(int const a,int const b)
9 {
10 return a>b?a:b;
11 }
12
13 int main()
14 {
15 int i,n,j,k;
16 while(scanf("%d",&n)!=EOF)
17 {
18 memset(dp,0,(n+1)*sizeof(int));
19 for(i=1;i<=n;i++)
20 {
21 for(j=1;j<=n;j++)
22 scanf("%d",&peo[i][j]);
23 }
24 for(i=1;i<=n;i++)
25 {
26 for(j=n;j>=0;j--)
27 {
28 for(k=0;k<=j;k++)
29 {
30 dp[k]=max(dp[k],dp[j-k]+peo[i][k]);
31 }
32 }
33
34 }
35 printf("%d\n",dp[n]);
36 }
37 return 0;
38 }
下面是有km最大匹配算法来做的。。。。
代码:
//二分图最佳匹配,kuhn munkras算法,邻接阵形式,复杂度O(m*n*m);
/*返回最佳匹配值,传入二分图的大小,m,n和邻接阵mat,表示权值
1 /*@coder龚细军*/
2 #include<stdio.h>
3 #include<string.h>
4 #define MAX 305
5 #define inf 1000000000
6
7 int km(int n, int mat[][MAX],int *match1,int *match2 )
8 {
9 int s[MAX],t[MAX],lx[MAX]={0},ly[MAX],p,q,ret=0,i,j,k;
10 for( i=0; i<n ; i++)
11 {
12 for(lx[i]=-inf,j=0 ; j<n ;j++)
13 {
14 lx[i]=mat[i][j]>lx[i]?mat[i][j]:lx[i];
15 }
16 }
17 memset(ly,0,n*sizeof(int)); /*节约大把的时间是不*/
18 memset(match1,0xff,sizeof(int)*n);
19 memset(match2,0xff,sizeof(int)*n);
20 for(i=0 ; i<n ;i++)
21 {
22 memset(t,0xff,sizeof(int)*n);
23 p=q=0;
24 for(s[p]=i;p<=q&&match1[i]<0 ; p++)
25 {
26 for(k=s[p],j=0; j<n&&match1[i]<0 ;j++)
27 {
28 if(lx[k]+ly[j]==mat[k][j]&&t[j]<0)
29 {
30 s[++q]=match2[j];
31 t[j]=k;
32 if(s[q]<0)
33 for(p=j ; p>=0 ; j=p)
34 {
35 match2[j]=k=t[j];
36 p=match1[k];
37 match1[k]=j;
38 }
39 }
40 }
41 }
42 if(match1[i]<0)
43 {
44 for(i--,p=inf,k=0; k<=q; k++)
45 {
46 for(j=0; j<n; j++)
47 {
48 if(t[j]<0&&lx[s[k]]+ly[j]-mat[s[k]][j]<p)
49 p=lx[s[k]]+ly[j]-mat[s[k]][j];
50 }
51 }
52 for(j=0;j<n;ly[j]+=t[j]<0?0:p,j++);
53 for(k=0; k<=q ; lx[s[k++]]-=p);
54 }
55 }
56 for(i=0;i<n;i++)
57 {
58 ret+=mat[i][match1[i]];
59 }
60 return ret;
61 }
62 int map[MAX][MAX],aa[MAX],bb[MAX];
63 int main()
64 {
65 int n,i,j;
66 while(scanf("%d",&n)!=EOF)
67 {
68 for(i=0;i<n;i++)
69 {
70 for(j=0;j<n;j++)
71 {
72 scanf("%d",&map[i][j]);
73 }
74 }
75 printf("%d\n",km(n,map,aa,bb));
76 }
77 return 0;
78 }