题解：机器任务问题

一、题目背景

有两台机器 (A) 和 (B)，分别有 (N) 种和 (M) 种不同模式，初始都处于模式 (0)。现有 (K) 个任务，每个任务可在 (A) 或 (B) 上执行，且在不同机器上执行需设置特定模式。每切换一次机器模式，机器就要重启一次。要求合理分配任务并安排顺序，使机器重启次数最少。

二、解题思路

本题可转化为二分图匹配问题。将机器 (A) 除模式 (0) 外的其他模式看作二分图的一侧节点，机器 (B) 除模式 (0) 外的其他模式看作另一侧节点。对于每个任务，如果在 (A) 上执行需要非 (0) 模式 (a)，在 (B) 上执行需要非 (0) 模式 (b)，则在模式 (a) 和模式 (b) 对应的节点之间连边。这样，求机器重启最少次数就相当于求这个二分图的最小点覆盖数，而根据二分图的性质，最小点覆盖数等于最大匹配数，所以使用匈牙利算法来求解最大匹配数。

具体步骤如下：
1. 定义相关数组和变量，包括存储二分图边关系的二维数组 g[N][N]（true 表示两个模式对应的节点有边相连）、记录匹配情况的数组 match[N]（存储每个节点的匹配对象）、标记节点是否已访问的数组 st[N]。
2. 编写匈牙利算法的核心函数 find，用于寻找增广路径：
- 遍历与当前节点 x 相连的所有节点 i。
- 检查节点 i 是否未被访问且与节点 x 有边相连。
- 标记节点 i 为已访问，若节点 i 未匹配，或者能通过递归找到增广路径，则更新匹配关系并返回 true。
- 若所有相连节点都无法找到增广路径，则返回 false。
3. 在 main 函数中：
- 循环读取测试数据，直到输入的 (n = 0) 结束。
- 读取机器 (A) 的模式数 (n)、机器 (B) 的模式数 (m) 和任务数 (k)，初始化二分图的边关系数组 g 和匹配数组 match。
- 读取每个任务的信息，若任务在机器上执行所需模式不为 (0)，则在相应模式节点间建立边关系。
- 遍历机器 (A) 的所有模式节点，调用 find 函数进行匹配尝试，若匹配成功则结果加 (1)。
- 输出最大匹配数，即机器最少重启次数。

三、代码逐段分析

（一）头文件和全局变量

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m, k;
int match[N];
bool g[N][N], st[N];

1. 头文件：
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
2. 常量定义：const int N = 110; 定义模式数量的最大值。
3. 变量定义：
   • int n, m, k;：分别表示机器 (A) 的模式数、机器 (B) 的模式数和任务数。
   • int match[N];：数组，存储机器 (B) 模式的匹配情况，match[i] 表示机器 (B) 的模式 (i) 匹配的机器 (A) 的模式，-1 表示未匹配。
   • bool g[N][N], st[N];：g[N][N] 表示二分图的边关系，true 表示两个模式对应的节点有边相连；st[N] 用于标记在一次匹配尝试中，机器 (B) 的模式节点是否已被访问。

（二）匈牙利算法函数 find

bool find(int x)
{
    for (int i = 0; i < m; i ++ )
        if (!st[i] && g[x][i])
        {
            st[i] = true;
            if (match[i] == -1 || find(match[i]))
            {
                match[i] = x;
                return true;
            }
        }

    return false;
}

1. 遍历机器 (B) 的所有模式节点 i：
   • 检查节点 i 是否未被访问（!st[i]）且与机器 (A) 的模式节点 x 有边相连（g[x][i]）。
2. 若节点 i 满足条件：
   • 标记节点 i 为已访问（st[i] = true;）。
   • 获取节点 i 当前的匹配情况 match[i]。
   • 若节点 i 未匹配（match[i] == -1），或者能通过递归调用 find 函数为节点 i 的当前匹配对象找到新的匹配（find(match[i])），则更新节点 i 的匹配为节点 x，并返回 true。
3. 若所有相连节点都无法找到增广路径，则返回 false。

（三）main 函数

int main()
{
    while (cin >> n, n)
    {
        cin >> m >> k;
        memset(g, 0, sizeof g);
        memset(match, -1, sizeof match);

        while (k -- )
        {
            int t, a, b;
            cin >> t >> 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;
}

1. 循环读取测试数据，当输入的机器 (A) 的模式数 n = 0 时结束循环。
2. 读取机器 (B) 的模式数 m 和任务数 k，初始化二分图的边关系数组 g（清零）和匹配数组 match（所有元素设为 -1）。
3. 读取每个任务的信息，包括任务编号 t，在机器 (A) 上执行所需模式 a 和在机器 (B) 上执行所需模式 b：
   • 若 a 或 b 为 (0)，则跳过该任务（因为模式 (0) 不需要重启机器）。
   • 否则，在模式 a 和模式 b 对应的节点间建立边关系（g[a][b] = true;）。
4. 初始化结果变量 res = 0，遍历机器 (A) 的所有模式节点 i：
   • 每次匹配尝试前，将访问标记数组 st 清零。
   • 调用 find 函数进行匹配尝试，若匹配成功（find(i) 返回 true），则结果 res 加 (1)。
5. 输出最大匹配数 res，即机器最少重启次数。
6. 程序结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 读入数据：读取任务信息，时间复杂度为 (O(k))，其中 (k) 是任务数量。
2. 匈牙利算法：对于机器 (A) 的每个模式节点，最多进行 (O(m)) 次匹配尝试（因为机器 (B) 有 (m) 个模式节点），而机器 (A) 有 (n) 个模式节点，所以匈牙利算法的时间复杂度为 (O(nm))。
   总体时间复杂度为 (O(k + nm))。

（二）空间复杂度

1. 数组空间：二分图边关系数组 g[N][N] 空间复杂度为 (O(nm))，匹配数组 match[N] 空间复杂度为 (O(m))，访问标记数组 st[N] 空间复杂度为 (O(m))。
   总体空间复杂度为 (O(nm))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。