博客

算法竞赛进阶指南，434页，二分图最小点覆盖

题目意思：

有两台机器A和B，分别有n种和m种不同的模式，有k个工作，每个工作都可以在那两个机器的某种特定的模式下处理。

如job0既可以在A机器的3好模式下处理，也可以在B机器的4号模式下处理。

机器的工作模式改变只能通过人工来重启。通过改变工作的顺序，和分配每个工作给合适的机器可以减少重启机器的次数达到最小。

任务就是计算那个最小的次数。初始时两台机器都运行在0号模式下

本题要点：

1、二分图最小点覆盖问题：

每个作业 i 可以以机器A 的 a[i]模式运行，也可以以机器A 的 b[i]模式运行.

以A机器的n种模式作为 左部节点，B机器m种模式作为右部节点， 每个作业 （连左部 第 a[i]节点，右部第 b[i]个节点）。

题目要求重启机器的次数最少，相当于用最少的点，来覆盖最多的边。也就是求二分图的最小点覆盖。

2、根据 konig 定理：二分图的最小店覆盖点数，等于二分图的最大匹配包含的边数。

求二分图的最大匹配的边数，用增广路算法。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 110;
int n, m, k;
int a[MaxN][MaxN], match[MaxN];
bool vis[MaxN];

bool dfs(int x)
{
	for(int y = 0; y < m; ++y)
	{
		if(!a[x][y] || vis[y])
			continue;
		vis[y] = true;
		if(match[y] == -1 || dfs(match[y]))
		{
			match[y] = x;
			return true;
		}
	}
	return false;
}

int main()
{
	int i, x, y;
	while(scanf("%d", &n) != EOF && n)
	{
		memset(a, 0, sizeof a);
		memset(match, -1, sizeof match);
		scanf("%d%d", &m, &k);
		for(int t = 0; t < k; ++t)
		{
			scanf("%d%d%d", &i, &x, &y);
			if(x * y != 0)
				a[x][y] = 1;
		}
		int ans = 0;
		for(int i = 0; i < n; ++i)
		{
			memset(vis, 0, sizeof vis);
			if(dfs(i))
			{
				++ans;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

/*
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
*/

/*
3
*/