奔小康賺大錢
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 } View Code
下面是有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 } View Code