Machine Schedule HDU 1150 二分图最大匹配(最小点覆盖)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1150

在这里插入图片描述

思路:

题目大概意思:有n个任务,需要在电脑的不同模式下进行,可以在A组电脑的i模式下进行或者在B组的j模式下进行,刚开始电脑处于0模式,所以对于其他模式需要重启电脑,其次对于0模式下的任务,我们就无需去判断
所以我们可以用二分图匹配,将A组模式看成一个集合,将B组模式看成一个集合,用A集合去匹配B集合,用尽量少的点使得覆盖所有的边,所以就是求最小顶点覆盖(最大匹配)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
int liner[105];
int used[105];
int n, m, k;
bool dfs(int u)
{
int m = g[u].size();
for(int i = 0; i < m; i++){
int v = g[u][i];
if(used[v] == 0){
used[v] = true;
// 如果该点还未匹配 否则 用v点去找是否存在增广路
if(liner[v] == -1 || dfs(liner[v])){
// 交换匹配
liner[v] = u;

return true;
}
}
}
return false;
}
int hungary()
{
// 记录最大匹配值
int ans = 0;
memset(liner, - 1, sizeof(liner));
for(int i = 1; i < n; i++){
memset(used, 0, sizeof(used));
// 找一条增广路
if(dfs(i)) ans++;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
while(cin >> n && n){
cin >> m >> k;
g.clear();
g.resize(n + 5);
for(int i = 1; i <= k; i++){
int a, b, c;
cin >> a >> b >> c;
if(b != 0 && c != 0){
// b为 左边, c 为 右边
g[b].push_back(c);
}
}
cout << hungary() << endl;
}
return 0;
}

本文标题:Machine Schedule HDU 1150 二分图最大匹配(最小点覆盖)

文章作者:HKer_YM

发布时间:2020年03月31日 - 13:28:39

最后更新:2020年03月31日 - 13:29:21

原始链接:https://blog.dreams-wj.top/2020/03/31/Machine-Schedule-HDU-1150-%E4%BA%8C%E5%88%86%E5%9B%BE%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8D-%E6%9C%80%E5%B0%8F%E7%82%B9%E8%A6%86%E7%9B%96/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。