文章目录
题意题解代码模板版本详细注释版本
题目连接 vj or hdu
题意
有 n 家老百姓 和 n 家房子, 每家都只能买一间房子, 而且房子都会卖出去, 求村领导最大收益
题解
非常感谢这位大佬的博客, 受益良多
代码
模板版本
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std
;
class Kuhn_Munkres {
public:
static const int MAXN
= 310;
static const int INF
= 0x3f3f3f3f;
int n
;
int graph
[MAXN
][MAXN
];
bool visx
[MAXN
], visy
[MAXN
];
int lx
[MAXN
], ly
[MAXN
], match
[MAXN
], slack
[MAXN
];
Kuhn_Munkres
( ) { };
Kuhn_Munkres
( int _n
) : n(_n
) { };
inline void add
( int u
, int v
, int w
) {
graph
[u
][v
] = w
;
}
inline void ini
( int n
) {
this->n
= n
;
memset( graph
, 0, sizeof(graph
) );
}
bool dfs
( int x
) {
visx
[x
] = true;
for ( int i
= 1; i
<= n
; i
++ ) {
if ( visy
[i
] )
continue;
int temp
= lx
[x
] + ly
[i
] - graph
[x
][i
];
if ( temp
== 0 ) {
visy
[i
] = true;
if ( match
[i
] == -1 || dfs
( match
[i
] ) ) {
match
[i
] = x
;
return true;
}
}
else if ( slack
[i
] > temp
)
slack
[i
] = temp
;
}
return false;
}
long long run
( ) {
memset
( match
, -1, sizeof ( match
) );
memset
( ly
, 0, sizeof ( ly
) );
int i
, j
, k
;
for ( i
= 1; i
<= n
; i
++ )
for ( j
= 1, lx
[i
] = -INF
; j
<= n
; j
++ )
if ( graph
[i
][j
] > lx
[i
] )
lx
[i
] = graph
[i
][j
];
for ( i
= 1; i
<= n
; i
++ ) {
memset
( slack
, 0x3f, sizeof ( slack
) );
while ( 1 ) {
memset
( visx
, 0, sizeof ( visx
) );
memset
( visy
, 0, sizeof ( visy
) );
if ( dfs
( i
) )
break;
int temp
= INF
;
for ( k
= 1; k
<= n
; k
++ )
if ( !visy
[k
] && temp
> slack
[k
] )
temp
= slack
[k
];
for ( j
= 1; j
<= n
; j
++ )
if ( visx
[j
] )
lx
[j
] -= temp
;
for ( int j
= 1; j
<= n
; j
++ )
if ( visy
[j
] )
ly
[j
] += temp
;
else
slack
[j
] -= temp
;
}
}
long long ans
= 0;
for ( int i
= 1; i
<= n
; i
++ )
ans
+= graph
[match
[i
]][i
];
return ans
;
}
}km
;
int main
( ) {
int n
,
w
;
while ( scanf
( "%d", &n
) != EOF ) {
km
.ini( n
);
for ( int i
= 1; i
<= n
; i
++ ) {
for ( int j
= 1; j
<= n
; j
++ ) {
scanf
( "%d", &w
);
km
.add( i
, j
, w
);
}
}
printf
( "%d\n", km
.run() );
}
return 0;
}
详细注释版本
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std
;
const int MAXN
= 305;
const int INF
= 0x3f3f3f3f;
int love
[MAXN
][MAXN
];
int ex_girl
[MAXN
];
int ex_boy
[MAXN
];
bool vis_girl
[MAXN
];
bool vis_boy
[MAXN
];
int match
[MAXN
];
int slack
[MAXN
];
int N
;
bool dfs(int girl
)
{
vis_girl
[girl
] = true;
for (int boy
= 0; boy
< N
; ++boy
) {
if (vis_boy
[boy
]) continue;
int gap
= ex_girl
[girl
] + ex_boy
[boy
] - love
[girl
][boy
];
if (gap
== 0) {
vis_boy
[boy
] = true;
if (match
[boy
] == -1 || dfs( match
[boy
] )) {
match
[boy
] = girl
;
return true;
}
} else {
slack
[boy
] = min(slack
[boy
], gap
);
}
}
return false;
}
int KM()
{
memset(match
, -1, sizeof match
);
memset(ex_boy
, 0, sizeof ex_boy
);
for (int i
= 0; i
< N
; ++i
) {
ex_girl
[i
] = love
[i
][0];
for (int j
= 1; j
< N
; ++j
) {
ex_girl
[i
] = max(ex_girl
[i
], love
[i
][j
]);
}
}
for (int i
= 0; i
< N
; ++i
) {
fill(slack
, slack
+ N
, INF
);
while (1) {
memset(vis_girl
, false, sizeof vis_girl
);
memset(vis_boy
, false, sizeof vis_boy
);
if (dfs(i
)) break;
int d
= INF
;
for (int j
= 0; j
< N
; ++j
)
if (!vis_boy
[j
]) d
= min(d
, slack
[j
]);
for (int j
= 0; j
< N
; ++j
) {
if (vis_girl
[j
]) ex_girl
[j
] -= d
;
if (vis_boy
[j
]) ex_boy
[j
] += d
;
else slack
[j
] -= d
;
}
}
}
int res
= 0;
for (int i
= 0; i
< N
; ++i
)
res
+= love
[ match
[i
] ][i
];
return res
;
}
int main()
{
while (~scanf("%d", &N
)) {
for (int i
= 0; i
< N
; ++i
)
for (int j
= 0; j
< N
; ++j
)
scanf("%d", &love
[i
][j
]);
printf("%d\n", KM());
}
return 0;
}
