原文链接：http://acm.hdu.edu.cn/showproblem.php?pid=1533
这个题也是KM算法，详解见上一篇文章，但是需要转化为KM模型，求出所有men到所有House的花费，构建成一个图，然后用KM就可以解了
代码：
C语言: 高亮代码由发芽网提供
#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 110
#define MAX(a,b) a>b?a:b
#define MIN(a,b) a>b?b:a
char map [ M ][ M ];
int num [ M ][ M ], match [ M ];
int w [ M ][ M ], lx [ M ], ly [ M ], sx [ M ], sy [ M ];
int m ,n;
struct point {
int
x
,
y;
} men [ M ], house [ M ];
int search( int u)
{
int
j;
sx
[
u
]
=
1;
for(
j
=
1;
j
<=n;
j
++)
if(
!
sy
[
j
]
&&
w
[
u
][
j
]
==
lx
[
u
]
+
ly
[
j
])
{
sy
[
j
]
=
1;
if(
!
match
[
j
] ||
search(
match
[
j
]))
{
match
[
j
]
=
u;
return
1;
}
}
return
0;
}
void KM_match()
{
int
i
,
j
,
k
,
min;
for(
i
=
1;
i
<=n;
i
++)
{
lx
[
i
]
=
w
[
i
][
1
];
for(
j
=
2;
j
<=n;
j
++)
lx
[
i
]
=
MAX(
lx
[
i
],
w
[
i
][
j
]);
}
memset(
ly
,
0
,
sizeof(
ly));
memset(
match
,
0
,
sizeof(
match));
for(
i
=
1;
i
<=n;
i
++)
{
while(
1)
{
memset(
sx
,
0
,
sizeof(
sx));
memset(
sy
,
0
,
sizeof(
sy));
if(
search(
i))
break;
min
=
2147483647;
for(
j
=
1;
j
<=n;
j
++)
if(
sx
[
j
])
{
for(
k
=
1;
k
<=n;
k
++)
if(
!
sy
[
k
])
min
=
MIN(
min
,
lx
[
j
]
+
ly
[
k
]
-
w
[
j
][
k
]);
}
for(
j
=
1;
j
<=n;
j
++)
if(
sx
[
j
])
lx
[
j
]
-=
min;
for(
j
=
1;
j
<=n;
j
++)
if(
sy
[
j
])
ly
[
j
]
+=
min;
}
}
}
int main()
{
int
i
,
j
,
flag1
,
flag2
,
sum;
while(
scanf(
"%d%d"
,
&
m
,
&n
),
m||n)
{
memset(
num
,
0
,
sizeof(
num));
flag1
=
flag2
=
0;
for(
i
=
0;
i
<
m;
i
++)
{
scanf(
"%s"
,
map
[
i
]);
#include<string.h>
#include<math.h>
#define M 110
#define MAX(a,b) a>b?a:b
#define MIN(a,b) a>b?b:a
char map [ M ][ M ];
int num [ M ][ M ], match [ M ];
int w [ M ][ M ], lx [ M ], ly [ M ], sx [ M ], sy [ M ];
int m ,n;
struct point {
} men [ M ], house [ M ];
int search( int u)
{
}
void KM_match()
{
}
int main()
{