匈牙利算法
匈牙利算法
适用于二分图最大匹配数
二分图
一个图的顶点属于集合x或者集合y,图的所有边一定是一端连接属于x的节点，另一端连接属于y的顶点。
1.最小顶点覆盖
求最少的点，让二分图的每一条边至少和一个顶点关联。就是用最少的点覆盖所有的边。 最小顶点覆盖数=最大匹配数（每个点只能和一个边匹配）
2.DAG(有向无环图)的最小路径覆盖
用最少的路径覆盖所有的点 最少路径数=顶点数-最大匹配数
3.最大独立集
顶点总数-最大匹配数
举例机器调度 杭电OJ 1150 Machine Schedule
有两台机器A和B以及N个需要运行的任务。每台机器有多种不同的模式（模式0到模式n-1），而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式ai，如果它在机器B上运行，则机器B需要设置为模式bj。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。开始两台机器处于模式0。
分析
本质上是一个求最小顶点覆盖的问题，但是注意有一个陷阱。机器初始状态为模式0，可以在输入时预处理这一种状态，直接忽略。 其余和婚配问题一样，有n个男生，有m个女生，有k组相互符合择偶条件，求最大匹配数量。用匈牙利算法可以求解。循环执行n遍dfs,如果能形成新的组合（其中包括直接组合和可能的变换），ans++。to_boy数组记录女生的目前可能配偶，vis数组非常重要，防止在一遍dfs内反复访问 。
源代码
#include <bits/stdc++.h>
using namespace std;
bool M[110][110];
int to_boy[110];
bool vis[110];
int m;
bool dfs(int cur)
{
for (int i = 1; i < m; i++)
{
if(M[cur][i] && !vis[i])
{
vis[i] = 1;
if(to_boy[i] == -1 || dfs(to_boy[i]))
{
to_boy[i] = cur;
return true;
}
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
while(true)
{
int n, k;
cin >> n;
if(n == 0)
break;
cin >> m >> k;
int t,x,y;
memset(M, 0, sizeof(M));
for (int i = 1; i <= k; i ++)
{
cin >> t;
cin >> x >> y;
if(x != 0 && y != 0)
M[x][y] = 1;
}
memset(to_boy, -1, sizeof(to_boy));
int ans = 0;
for (int i = 1; i < n; i++)
{
memset(vis, 0, sizeof(vis));
if(dfs(i))
ans++;
}
cout << ans;
}
return 0;
}