c#如何实现匈牙利算法

Question

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 } };

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

Answer 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);
        }
    }
}

3
Press any key to continue . . .