学步园

思路：第一种想法：这道题可以转化为求最小费用 设一个超级源点把人连起来，各超级汇点把房间连起来，然后求解
 第二种想法：求最佳匹配（权值最小）然后就是KM算法
PS:忘了取反，检查了半天！！

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define M 105
#define inf 0x3f3f3f3f
int link[M],lx[M],ly[M];
int nv,visx[M],visy[M],dis[M],w[M][M];
char map[M][M];
struct node
{
    int
x,y;
}man[M],home[M];

int DFS (int x)
{
    visx[x] =
1;
    for (int y =
1;y <= nv;y ++)
    {
       
if (visy[y])
           
continue;
       
int t = lx[x] + ly[y] - w[x][y];
       
if (t == 0)
       
{
           
visy[y] = 1;
           
if (link[y] == -1||DFS(link[y]))
           
{
               
link[y] = x;
               
return 1;
           
}
       
}
       
else if (dis[y] > t)
           
dis[y] = t;
    }
    return
0;
}
int KM()
{
    int
i,j;
    memset
(link,-1,sizeof(link));
    memset
(ly,0,sizeof(ly));
    for (i = 1;i
<= nv;i ++)
       
for (j = 1,lx[i] = -inf;j <= nv;j ++)
           
if (w[i][j] > lx[i])
               
lx[i] = w[i][j];
    for (int x =
1;x <= nv;x ++)
    {
       
for (i = 1;i <= nv;i ++)
           
dis[i] = inf;
       
while (1)
       
{