开发者社区> 问答> 正文

如何实现匈牙利算法 c#问题

int[,] leader = new int[,] {{ 1,2,3},//第一个队长对老师的选择 
                            { 1,2,4},  //第二个队长对老师的选择 
                            { 1,3,4 }}; //第三个队长对老师的选择

 int[,] teacher = new int[,]{{ 1,2 },//老师选择学生
                             { 1,3 },
                             { 1,3 },
                             { 2,3 } };


两个二维数组,怎么写匈牙利算法,算出第几个队长匹配第几个老师

展开
收起
海边一只船 2020-05-28 13:28:07 1049 0
1 条回答
写回答
取消 提交回答
  • 用 https://zhuanlan.zhihu.com/p/96229700 这个程序改的

    
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace Q1064227
    {
        class Program
        {
            static int M, N;            //M, N分别表示左、右侧集合的元素数量
            static int[][] Map = new int[100][]; //邻接矩阵存图
            static int[] p = new int[100];         //记录当前右侧元素所对应的左侧元素
            static bool[] vis = new bool[100];      //记录右侧元素是否已被访问过
    
            static bool match(int i)
            {
                for (int j = 1; j <= N; ++j)
                    if (Map[i][j]!=0 && !vis[j]) //有边且未访问
                    {
                        vis[j] = true;                 //记录状态为访问过
                        if (p[j] == 0 || match(p[j])) //如果暂无匹配,或者原来匹配的左侧元素可以找到新的匹配
                        {
                            p[j] = i;    //当前左侧元素成为当前右侧元素的新匹配
                            return true; //返回匹配成功
                        }
                    }
                return false; //循环结束,仍未找到匹配,返回匹配失败
            }
    
            static int Hungarian()
            {
                int cnt = 0;
                for (int i = 1; i <= M; ++i)
                {
                    vis = vis.Select(x => false).ToArray();
                    if (match(i))
                        cnt++;
                }
                return cnt;
            }
    
            static void Main(string[] args)
            {
                Map = Map.Select(x => new int[100]).ToArray();
                int[,] leader = new int[,] {{ 1,2,3},//第一个队长对老师的选择 
                                { 1,2,4},  //第二个队长对老师的选择 
                                { 1,3,4 }}; //第三个队长对老师的选择
    
                int[,] teacher = new int[,]{{ 1,2 },//老师选择学生
                                 { 1,3 },
                                 { 1,3 },
                                 { 2,3 } };
                M = leader.GetLength(0);
                N = teacher.GetLength(0);
                for (int i = 0; i < leader.GetLength(0); i++)
                    for (int j = 0; j < leader.GetLength(1); j++)
                    {
                        Map[i+1][leader[i,j]]++;
                    }
                for (int i = 0; i < teacher.GetLength(0); i++)
                    for (int j = 0; j < teacher.GetLength(1); j++)
                    {
                        Map[teacher[i,j]][i+1]++;
                    }
                Map = Map.Select(x => x.Select(y => y == 2 ? 1 : 0).ToArray()).ToArray();
                int result = Hungarian();
                Console.WriteLine(result);
            }
        }
    }
    
    
    2020-05-29 19:03:39
    赞同 展开评论 打赏
问答分类:
问答标签:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载