[数据结构与算法]1150 Machine Schedule

题目详情：

Machine Schedule

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12936????Accepted Submission(s): 6437

?

题目大意：

两个机器，有多种模式，每个机器都可以重启切换模式，机器默认模式是模式0，现有多种任务，每个任务对应一种模式，问两个机器最少需要重启多少次才可以完成这些任务。

解题思路：

匈牙利算法，此题可以转化成二分图的最大匹配。

AC代码：

#include <iostream>
#include <vector>
#include <cstring>
#define MAX 101
using namespace std;
vector<int> unvisit(MAX, 1); //存放是否访问过
vector<int> bo_f(MAX, -1);   //女生的男朋友
bool dfs(vector<vector<int>> &machine, int b_w, int n, int m){
    for (int i = 0; i < m; ++i){
        if (machine[b_w][i] && unvisit[i]){ //传过来的男生有女朋友且该女生没有访问过
            unvisit[i] = 0;
            if (bo_f[i] == -1 || dfs(machine, bo_f[i], n, m)){ //该女生没有男朋友且dfs后为真
                bo_f[i] = b_w;
                return true;
            }
        }
    }
    return false;
}
int xyl(vector<vector<int>> &machine, int n, int m){
    int s = 0;
    for (int i = 0; i < n; ++i){
        fill(unvisit.begin(), unvisit.end(), 1);
        if (dfs(machine, i, n, m))  ++s;
    }
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    int i, x, y;
    while (cin >> n && n){
        cin >> m >> k;
        vector<vector<int>> machine(MAX, vector<int>(MAX, 0)); //邻接矩阵
        fill(unvisit.begin(), unvisit.end(), 1);
        fill(bo_f.begin(), bo_f.end(), -1);
        while (k--){
            cin >> i >> x >> y;
            if (x != 0 && y != 0)
                machine[x][y] = 1;
        }
        cout << xyl(machine, n, m) << endl;
    }
    return 0;
}