UVa 1194 & POJ 1325 Machine Schedule

題意：
    有A,B兩台機器，A的mode從0~n-1，B的mode從0~m-1，現在有k個job，底下有k行，每行有三個數i,x,y表示第i個job，A機器需用mode(x)完成這項工作，B機器則是需用mode(y)，一向工作只需交給A或B其中一個即可。有個規則是A,B這兩台機器變換mode的時候需要restart一次，例如mode(1)變成mode(10)需要restart一次，一開始兩台機器都是從mode(0)開始，問如何分配工作給A或B使得總restart次數最小，並輸出restart次數。

想法：
    一件工作x,y如果選x則不用y，反之選y就不用x，但都是要restart一次，因此可以想到最大匹配數，如果x或y其中一個已經匹配好了，表示A或B其中之一已經restart一次，則這件job就可以跳過。
    具體做法是，將第i個工作x放到左邊那群，y放到右邊那群，並建立(x,y)這條邊，然後套模板求最大匹配數就是答案。注意讀入測資的時候如果x或y其中是0，則直接跳過不用建邊，因為機器從mode(0)開始。


UVa版：

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector<int> edge[105];
	int llink[105], rlink[105];
	bool used[105];
	bool dfs(int now)
	{
	for (int nxt : edge[now]) {
	if (used[nxt]) continue;
	used[nxt] = true;
	if (rlink[nxt] == -1 || dfs(rlink[nxt]) == true) {
	llink[now] = nxt;
	rlink[nxt] = now;
	return true;
	}
	}
	return false;
	}
	int main()
	{
	int n, m, k;
	while (scanf("%d", &n) && n) {
	for (auto &v : edge) v.clear();
	// Input
	scanf("%d %d", &m, &k);
	int i, x, y;
	for (int j = 0; j < k; ++j) {
	scanf("%d %d %d", &i, &x, &y);
	if (!x || !y) continue; // mode 0直接忽略!
	edge[x].push_back(y);
	}
	// Bipartite
	int result = 0;
	fill(begin(llink), end(llink), -1);
	fill(begin(rlink), end(rlink), -1);
	for (int i = 0; i < n; ++i) {
	fill(begin(used), end(used), false);
	if (dfs(i) == true) ++result;
	}
	// Output
	printf("%d\n", result);
	}
	}

view raw [UVa] 1194 Machine Schedule.cpp hosted with ❤ by GitHub

POJ版：

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector<int> edge[105];
	int llink[105], rlink[105];
	bool used[105];
	bool dfs(int now)
	{
	for (int i = 0; i < edge[now].size(); ++i) {
	int nxt = edge[now][i];
	if (used[nxt]) continue;
	used[nxt] = true;
	if (rlink[nxt] == -1 || dfs(rlink[nxt]) == true) {
	llink[now] = nxt;
	rlink[nxt] = now;
	return true;
	}
	}
	return false;
	}
	int main()
	{
	int n, m, k;
	while (scanf("%d", &n) && n) {
	for (int i = 0; i < n; ++i) edge[i].clear();
	// Input
	scanf("%d %d", &m, &k);
	int i, x, y;
	for (int j = 0; j < k; ++j) {
	scanf("%d %d %d", &i, &x, &y);
	if (!x || !y) continue; // mode 0直接忽略!
	edge[x].push_back(y);
	}
	// Bipartite
	int result = 0;
	fill(llink, llink+n, -1);
	fill(rlink, rlink+m, -1);
	for (int i = 0; i < n; ++i) {
	fill(used, used+m, false);
	if (dfs(i) == true) ++result;
	}
	// Output
	printf("%d\n", result);
	}
	}

view raw [POJ] 1325 Machine Schedule.cpp hosted with ❤ by GitHub