POJ1325 Machine Schedule（二分图最小点覆盖）

╰半橙微兮° 2021-11-09 23:44 277阅读 0赞

## 题意：有两台机器A,B及N个任务。每台机器有M种不同的模式。M,N <= 100。对每个任务i给定a\[i\]和b\[i\]，表示如果该任务在A上执行，需要设置模式为a\[i\]，如果在B上执行，需要模式为b\[i\]。任务可以以任意顺序被执行。但每台机器转换一次模式就要重启一次。要求合理分配任务并合理安排顺序，使得机器重启次数最少。 ##

# #

## 分析：具有“2要素”的特点，可抽象成二分图最小覆盖模型求解。详见《算法竞赛进阶指南》P429。 ##

## 代码： ##

#include <cstdio>
    #include <vector>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int N = 106;
    int n, m, k, f[N], ans;
    bool v[N];
    vector<int> e[N];
    
    bool dfs(int x) {
    	for (unsigned int i = 0; i < e[x].size(); i++) {
    		int y = e[x][i];
    		if (v[y]) continue;
    		v[y] = 1;
    		if (!f[y] || dfs(f[y])) {
    			f[y] = x;
    			return 1;
    		}
    	}
    	return 0;
    }
    
    inline void Machine_Schedule() {
    	cin >> m >> k;
    	for (int i = 1; i < n; i++) e[i].clear();
    	for (int i = 0; i < k; i++) {
    		int x, y;
    		scanf("%d %d %d", &i, &x, &y);
    		if (x && y) e[x].push_back(y);
    	}
    	memset(f, 0, sizeof(f));
    	ans = 0;
    	for (int i = 1; i < n; i++) {
    		memset(v, 0, sizeof(v));
    		ans += dfs(i);
    	}
    	cout << ans << endl;
    }
    
    int main() {
    	while (cin >> n && n) Machine_Schedule();
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，277人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 1274 The Perfect Stall（二分图 && 匈牙利 && 最小点覆盖）

嗯... 题目链接：http://poj.org/problem?id=1274 一道很经典的匈牙利算法的题目：将每只奶牛看成二分图中左边的点，将牛圈看成二

待我称王封你为后i/ 2023年06月04日 13:57/ 0 赞/ 33 阅读

相关 hdu 题目1150 Machine Schedule（最小点覆盖）

[http://acm.hdu.edu.cn/showproblem.php?pid=1150 ][http_acm.hdu.edu.cn_showproblem.php_

冷不防/ 2022年12月22日 08:40/ 0 赞/ 205 阅读

相关 POJ 1325-Machine Schedule（二分图匹配-匈牙利算法）

Machine Schedule <table> <tbody> <tr> <td><strong>Time Limit:</strong> 10

快来打我*/ 2022年09月25日 08:28/ 0 赞/ 201 阅读

相关二分图之最小边覆盖（poj3020）

题目：[poj3020][] 题意：给出一个图，让你用最少的1\2的纸片覆盖掉图中的所有\出现过的地方。基本裸的最小边覆盖。分析：最小边覆盖 =

我不是女神ヾ/ 2022年08月27日 14:54/ 0 赞/ 179 阅读

相关 Machine Schedule（最小点覆盖数）

Machine Schedule Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

- 日理万妓/ 2022年08月01日 06:09/ 0 赞/ 160 阅读

相关 HDU3360-二分图最小点覆盖

National Treasures Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/3276

偏执的太偏执、/ 2022年07月12日 07:25/ 0 赞/ 193 阅读

相关 HDU3360-二分图最小点覆盖

National Treasures Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/3276

ゝ一世哀愁。/ 2022年07月12日 07:25/ 0 赞/ 178 阅读

相关 HDU1528-二分图最小点覆盖

Card Game Cheater Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

我不是女神ヾ/ 2022年07月12日 07:20/ 0 赞/ 180 阅读

相关 HDU1528-二分图最小点覆盖

Card Game Cheater Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

Love The Way You Lie/ 2022年07月12日 07:20/ 0 赞/ 178 阅读

相关 POJ1325 Machine Schedule（二分图最小点覆盖）

题意：有两台机器A,B及N个任务。每台机器有M种不同的模式。M,N <= 100。对每个任务i给定a\[i\]和b\[i\]，表示如果该任务在A上执行，需要设置模式为a\[i

╰半橙微兮°/ 2021年11月09日 23:44/ 0 赞/ 278 阅读