hdu 2255 奔小康赚大钱

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 
 6 const int N=301;
 7 int n;
 8 int grid[N][N];
 9 int expx[N];
10 int expy[N];
11 int matH[N];
12 int matP[N];
13 int visitedH[N];
14 int visitedP[N];
15 int sub;
16 
17 bool dfs(int u){
18     visitedP[u]=1;
19     for(int i=0;i<n;++i){
20         if(visitedH[i]) continue;
21         int diff=expx[u]+expy[i]-grid[u][i];
22         if(diff==0){
23             visitedH[i]=1;
24             if(matP[i]==-1 || dfs(matP[i])){
25                 matP[i]=u;
26                 matH[u]=i;
27                 return true;
28             }
29         }else{
30             sub=min(sub,diff);
31         }
32     }
33     return false;
34 }
35 
36 int KM(){
37     for(int i=0;i<n;++i){
38         while(true){
39             memset(visitedH,0,sizeof(visitedH));
40             memset(visitedP,0,sizeof(visitedP));
41             sub=INT_MAX;
42             if(dfs(i)) break;
43 
44             for(int p=0;p<n;++p){
45                 if(visitedP[p]) expx[p]-=sub;
46                 if(visitedH[p]) expy[p]+=sub;
47             }
48         }
49     }
50     int res=0;
51     for(int i=0;i<n;++i){
52         int j=matH[i];
53         res+=grid[i][j];
54     }
55     return res;
56 }
57 
58 int main(){
59     while(scanf("%d",&n)!=EOF){
60         memset(matH,-1,sizeof(matH));
61         memset(matP,-1,sizeof(matP));
62         memset(visitedH,0,sizeof(visitedH));
63         memset(visitedP,0,sizeof(visitedP));
64         for(int i=0;i<n;++i){
65             expx[i]=0;
66             expy[i]=0;
67             for(int j=0;j<n;++j){
68                 scanf("%d", &grid[i][j]);
69                 expx[i]=max(expx[i],grid[i][j]);
70             }
71         }
72         int res=KM();
73         printf("%d\n",res);
74     }
75 }