求KM算法的matlab实现 急

matlab跟C差不多的，我会C，但是matlab不是很熟悉，举携怕误导你，就不团答敏写matlab的了，把C的给你

const int maxn=20,INF=2147483647

int w[maxn][maxn]

int lx[maxn]={0},ly[maxn]={0}//顶标

int linky[maxn]

int visx[maxn],visy[maxn]

int lack

bool find(int x){

visx[x]=true

for(int y=0y<maxny++){

if(visy[y])continue

int t=lx[x]+ly[y]-w[x][y]

if(t==0){

visy[y]=true

if(linky[y]==-1||find(linky[y])){

linky[y]=x

return true

}

}

else if(lack>t)lack=t

}

return false

}

void KM(){

memset(linky,-1,sizeof(linky))

for(int i=0i<maxni++)

for(int j=0j<maxnj++)

if(w[i][j]>lx[i])

lx[i]=w[i][j]//初始化顶标

for(int x=0x<maxnx++){

for(){

memset(visx,0,sizeof(visx))

memset(visy,0,sizeof(visy))

lack=INF

if(find(x))break

for(int i=0i<maxni++){

if(visx[i])lx[i]-=lack

if(visy[i])ly[i]+=lack

}

}

}

}

希望可以塌枝帮到你，不懂再问哈~

我学pascal的。本来我是有程序的。既然你要c的那我只好查给你了。问算法过程的话可以追问匈牙利算法1 #include<stdio.h>

2 #include<string.h>

3 bool g[201][201]

4 int n, m, ans

5 bool b[201]

6 int link[201]

7 bool init()

8 {

9 int _x, _y

10 memset(g, 0, sizeof(g))

11 memset(link, 0, sizeof(link))

12 ans = 0

13 if (scanf("%d%d", &n, &m) == EOF)

14 return false

15 for (int i = 1i <= ni++) {

　散橡　16 scanf("%d", &_x)

17 for (int j = 0j <_xj++) {

18 scanf("%d", &_y)

19 g[i][_y] = true

20 }

21 }

22 return true

23 }

24

25 bool find(int a)

26 {

27 for (int i = 1i <= mi++) {

28 if (g[a][i] == 1 &&!b[i]) {

29 b[i] = true

30 if (link[i] == 0 || find(link[i])) {

31 link[i] = a

32 return true

33 }

34 }

35 }

36 return false

37 }

38

39 int main()

40 {

41 while (init()) {

42 for (int i = 1i <= ni++) {

43 memset(b, 0, sizeof(b))

44 if (find(i))

45 ans++

46 }

47 printf("%d\n", ans)

48 }

49 }KM算法#include <cstdio>

#include <memory.h>

#include <algorithm> // 使用其中的 min 函数

using namespace std

const int MAX = 1024

int n // X 的大小

int weight [MAX] [MAX] // X 到 Y 的映射（权重）

int lx [MAX], ly [MAX] // 标号

bool sx [MAX], sy [MAX] // 是否被搜索过

int match [MAX] // Y(i) 与 X(match [i]) 匹配

// 初始化权重

void init (int size)

// 从 X(u) 寻找冲消旁增广道路，找到桥贺则返回 true

bool path (int u)

// 参数 maxsum 为 true ，返回最大权匹配，否则最小权匹配

int bestmatch (bool maxsum = true)

void init (int size)

{

// 根据实际情况，添加代码以初始化

n = size

for (int i = 0i <ni ++)

for (int j = 0j <nj ++)

scanf ("%d", &weight [i] [j])

}

bool path (int u)

{

sx [u] = true

for (int v = 0v <nv ++)

if (!sy [v] &&lx[u] + ly [v] == weight [u] [v])

{

sy [v] = true

if (match [v] == -1 || path (match [v]))

{

match [v] = u

return true

}

}

return false

}

int bestmatch (bool maxsum)

{

int i, j

if (!maxsum)

{

for (i = 0i <ni ++)

for (j = 0j <nj ++)

weight [i] [j] = -weight [i] [j]

}

// 初始化标号

for (i = 0i <ni ++)

{

lx [i] = -0x1FFFFFFF

ly [i] = 0

for (j = 0j <nj ++)

if (lx [i] <weight [i] [j])

lx [i] = weight [i] [j]

}

memset (match, -1, sizeof (match))

for (int u = 0u <nu ++)

while (1)

{

memset (sx, 0, sizeof (sx))

memset (sy, 0, sizeof (sy))

if (path (u))

break

// 修改标号

int dx = 0x7FFFFFFF

for (i = 0i <ni ++)

if (sx [i])

for (j = 0j <nj ++)

if(!sy [j])

dx = min (lx[i] + ly [j] - weight [i] [j], dx)

for (i = 0i <ni ++)

{

if (sx [i])

lx [i] -= dx

if (sy [i])

ly [i] += dx

}

}

int sum = 0

for (i = 0i <ni ++)

sum += weight [match [i]] [i]

if (!maxsum)

{

sum = -sum

for (i = 0i <ni ++)

for (j = 0j <nj ++)

weight [i] [j] = -weight [i] [j]// 如果需要保持 weight [ ] [ ] 原来的值，这里需要将其还原

}

return sum

}

int main()

{

int n

scanf ("%d", &n)

init (n)

int cost = bestmatch (true)

printf ("%d ", cost)

for (int i = 0i <ni ++)

{

printf ("Y %d ->X %d ", i, match [i])

}

return 0

}

---