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 } };
两个二维数组,怎么写匈牙利算法,算出第几个队长匹配第几个老师
用 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);
}
}
}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。