Acwing 376.机器任务
题意
有两台机器 A，B以及 K 个任务。
机器 A 有 N种不同的模式（模式0 ∼ N − 1 ），机器 B 有 M 种不同的模式（模式 0 ∼ M − 1）。
两台机器最开始都处于模式 0。
每个任务既可以在 A上执行，也可以在 B 上执行。
对于每个任务 i，给定两个整数a[i] 和b[i]，表示如果该任务在A 上执行，需要设置模式为 a[i]，如果在B 上执行，需要模式为b[i]。
任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
求怎样分配任务并合理安排顺序，能使机器重启次数最少。
思路
将机器A的所有模式看作左边的集合，机器B 的所有模式看作右边的集合，模式看作顶点，任务看作连接机器 A 和机器 B 的一条边，原题可以抽象成一个二分图。那么题目要求的就是，在这张二分图中最少选多少个顶点（模式），可以覆盖所有的边（任务），即最小点覆盖问题。 而我们又知道在二分图中 最小点覆盖 == 最大匹配数，所以直接用匈牙利算法求二分图的最大匹配即可。
需要注意的是，两台机器最初都处于模式0，所以不用转换模式即可将a[i] 或b[i] 为0的任务完成，所以建图时将这种情况忽略即可。
代码
// Author：zzqwtcc // Problem: 机器任务 // Contest: AcWing // Time：2021-10-07 14:17:44 // URL: https://www.acwing.com/problem/content/378/ // Memory Limit: 10 MB // Time Limit: 1000 ms #include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 110; int n,m,k; vector<int>vec[N]; bool st[N]; int match[N]; bool find(int u){ for(int i =0 ; i < vec[u].size();++i){ int j =vec[u][i]; if(st[j])continue; st[j] = true; if(match[j] == -1 || find(match[j])){ match[j] = u; return true; } } return false; } void solve() { while(cin >> n, n){ for(int i = 0 ;i <= 100;++i)vec[i].clear(); memset(match,-1,sizeof match); cin >> m >> k; while(k--){ int id,u,v;cin >> id >> u >> v; if(u && v) vec[u].push_back(v); } int res = 0; for(int i = 0; i <= n;++i){ memset(st,0,sizeof st); if(find(i)) res++; } for(int i = 0; i <= m;++i){ if(match[i] == 0){ res--; break; } } cout << res << endl; } } signed main() { // int _; cin >> _; // while (_--) solve(); return 0; }
