二分图最大匹配 二分图最小点覆盖 T3 376. 机器任务 - AcWing题库 有两台机器 以及 个任务。
机器 有 种不同的模式（模式 ），机器 有 种不同的模式（模式 ）。
两台机器最开始都处于模式 。
每个任务既可以在 上执行，也可以在 上执行。
对于每个任务 ，给定两个整数 和 ，表示如果该任务在 上执行，需要设置模式为 ，如果在 上执行，需要模式为 。
任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
求怎样分配任务并合理安排顺序，能使机器重启次数最少。
输入格式
输入包含多组测试数据。
每组数据第一行包含三个整数 。
接下来 行，每行三个整数 和 ， 为任务编号，从 开始。
当输入一行为 时，表示输入终止。
输出格式
每组数据输出一个整数，表示所需的机器最少重启次数，每个结果占一行。
数据范围
输入样例：
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0输出样例：
3思路
最小点覆盖问题是一个图论中的问题，给定一个无向图，找出一个顶点集合，使得包含了所有边的至少一个端点，并且U的大小最小。如果每个顶点有一个权值，那么问题就变成了找出权值之和最小的顶点覆盖。 例如在有向无环图中，求能够覆盖所有顶点的最少简单路径的条数，或者在无线传感器网络中，求能够监测所有区域的最少传感器数量。
假设有一个无向图，如下图所示：
A---B
/ \ / \
C---D---E这个图的最小点覆盖是，因为这两个点可以覆盖所有的边，而且没有更小的点集可以做到这一点。
如果求二分图上的最小点覆盖问题，有一个重要的定理可以帮助我们，那就是Konig定理。 这个定理说的是，在一个二分图中，最小点覆盖的大小等于最大匹配的大小。
因此, 使用匈牙利算法求出的二分图最大匹配数就是最小点覆盖数。
而该题要求每个任务, 即每条边都至少有一个点选中, 也就是最小点覆盖问题。可以直接套模板求解。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 110;
int g[N][N];
int match[N];
int n,m,k;
bool st[N];
bool find(int u)
{
for(int i = 0; i < m; i++)
{
if(g[u][i] && !st[i])
{
st[i] = true;
if(match[i] == -1 || find(match[i]))
{
match[i] = u;
return true;
}
}
}
return false;
}
int main()
{
while(cin >> n,n)
{
cin >> m >> k;
memset(match, -1, sizeof match);
memset(g, 0, sizeof g);
while(k--)
{
int a, b, c;
cin >> c >> a >> b;
if(!a || !b) continue;
g[a][b] = true;
}
int res = 0;
for(int i = 0; i < n; i++)
{
memset(st, 0, sizeof st);
if(find(i))
res++;
}
cout << res << endl;
}
return 0;
}