本文主要是介绍POJ 1325 Machine Schedule 最小点覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
机器A的所有模式为左部顶点，机器B的所有模式为右部顶点，然后A与B之间的每条连线代表一个任务或工作
之后就要完成所有的任务，即将每条边都覆盖
对一个有向图，若要覆盖每条边，至少需要的点数为二分图最大匹配数
建图的方法还是拆点。
代码如下
/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 105
#define INF 1000000000
using namespace std;
int nx, ny;
vector<int>g[MAXN];
int cx[MAXN], cy[MAXN];
int mark[MAXN];
int path(int u)
{int x = g[u].size();for(int i = 0; i < x; i++){int v = g[u][i];if(!mark[v]){mark[v] = 1;if(cy[v] == -1 || path(cy[v])){cx[u] = v;cy[v] = u;return 1;}}}return 0;
}
int maxmatch()
{int res = 0;memset(cx, -1, sizeof(cx));memset(cy, -1, sizeof(cy));for(int i = 1; i <= nx; i++){if(cx[i] == -1){memset(mark, 0, sizeof(mark));res += path(i);}}return res;
}
int main()
{while(scanf("%d", &nx) != EOF && nx){int t, x, y;nx--;for(int i = 0; i <= nx; i++)g[i].clear();scanf("%d%d", &ny, &t);ny--;while(t--){scanf("%*d%d%d", &x, &y);if(!x || !y) continue;g[x].push_back(y);}printf("%d\n", maxmatch());}return 0;
}这篇关于POJ 1325 Machine Schedule 最小点覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
