使用匈牙利算法求解

	 

	#include<stdio.h> 

	#include<string.h> 

	int adj_vex[501][501]; 

	int match[501]; 

	int flag[501]; 

	 

	int find(int v, int n) 

	{ 

	    int i; 

	    for (i = 1; i <= n; i++) 

	    { 

	        if (adj_vex[v][i] == 1 && flag[i] == 0) 

	        { 

	            flag[i] = 1; 

	            if (match[i] == 0 || find(match[i], n) == 1) 

	            { 

	                match[i] = v; 

	                return 1; 

	            } 

	        } 

	    } 

	    return 0; 

	} 

	 

	void main() 

	{ 

	    int k, m, n; 

	    int i, j, male, female; 

	    int count; 

	//    freopen("input.txt", "r", stdin); 

	    while (scanf("%d", &k) != EOF && k != 0) 

	    { 

	        scanf("%d%d", &m, &n); 

	        for (i = 1; i <= m; i++) 

	        { 

	            for (j = 1; j <= n; j++) 

	            { 

	                adj_vex[i][j] = 0; 

	            } 

	        } 

	 

	        for (i = 1; i <= k; i++) 

	        { 

	            scanf("%d%d", &male, &female); 

	            adj_vex[male][female] = 1; 

	        } 

	        count = 0; 

	        memset(match, 0, (n + 1)*sizeof(int)); 

	        for (i = 1; i <= m; i++) 

	        { 

	            memset(flag, 0, (n + 1)*sizeof(int)); 

	            if (find(i, n) == 1) 

	                count++; 

	        } 

	        printf("%d\n",count); 

	    } 

	}   

补充：软件开发 , C语言 ,

上一个：Bone Collector
下一个：fork与进程地址空间