Machine Schedule POJ - 1325（二分匹配， 最小点覆盖）

本文主要是介绍Machine Schedule POJ - 1325（二分匹配， 最小点覆盖），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接： POJ - 1325

题意：k个job， 2个机器A， B， 初始状态都是0模式， 每个工作可以在A机器的x模式或B机器的y模式下完成， 求最少重启几次机器可以完成所有工作；

因为初始状态是0模式， 所以可以在0模式下完成的工作不需要记录， 对AB的模式建边， 如果j工作可以在A的x或B的y下完成， xy建边；求一个最小点覆盖， 即二分图的最大匹配；

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
const int maxn=105;
int n, m, k;
int nx[maxn], my[maxn], match[maxn][maxn];
bool vis[maxn];
bool dfs(int u){for(int i=0; i<m; i++){if(match[u][i]&&!vis[i]){vis[i]=true;if(!my[i]||dfs(my[i])){my[i]=u;nx[u]=i;return true;}}}return false;
}
int max_match(){int ans=0;for(int i=0; i<n; i++){memset(vis, false, sizeof(vis));if(dfs(i)) ans++;}return ans;
}
int main(){while(scanf("%d", &n), n){scanf("%d%d", &m, &k);memset(nx, 0, sizeof(nx));memset(match, 0, sizeof(match));memset(my, 0, sizeof(my));int x, y, j, cnt=0;for(int i=0; i<k; i++){scanf("%d%d%d", &j, &x, &y);if(x==0||y==0) continue;match[x][y]=1;}int ans=max_match();printf("%d\n", ans);}return 0;
}

这篇关于Machine Schedule POJ - 1325（二分匹配， 最小点覆盖）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---