Description
Input
Output
Sample Input
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
Sample Output
3
之所以把题目粘下来是因为自己读题不仔细wa一次
大意：
有两台机器分别有n，m种模式，开始的时候全都在0模式
告诉你有一些任务可以在第一台机器的x1模式下完成也可以在第二台机器的x2模式下完成
并且每台机器切换模式需要重启
问最少重启多少次
分析：
左右集合分别为两台机器的模式
边为task
那么只要选取最少的点覆盖所有的边即可
注意一点是一开始在0模式
所以只要对于0不建边即可
网络流亦可以做
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 105; int n; vector<int> G[maxn]; int vis[maxn]; int Link[maxn]; bool Find(int u) { for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(!vis[v]) { vis[v] = 1; if(Link[v] == -1 || Find(Link[v])) { Link[v] = u; return true; } } } return false; } int solve() { int cnt = 0; memset(Link, -1, sizeof(Link)); for(int i = 0; i < n; i++) { memset(vis, 0, sizeof(vis)); if(Find(i)) cnt++; } return cnt; } int main() { int m, k; int a, b, c; while(scanf("%d",&n) && n) { scanf("%d %d",&m, &k); n = max(n, m); for(int i = 0; i < n; i ++) G[i].clear(); for(int i = 0; i < k; i++) { scanf("%d %d %d",&a, &b, &c); if(b == 0 || c == 0) continue; G[b].push_back(c); } printf("%d\n",solve()); } return 0; }
POJ 1325 Machine Schedule【最小点覆盖】,布布扣,bubuko.com
POJ 1325 Machine Schedule【最小点覆盖】
原文：http://www.cnblogs.com/zhanzhao/p/3920310.html
