题意
给你两台机器和k个工件,要你设计最优调度方案。对于每个机器,一共有0 ~ n-1(或者是m-1)这n(或者是m)个状态,初始状态都是0。对于每个工件,要么在x号状态下加工,要么在y号状态下加工。你要给出两台机器一共最少要切换多少次状态,才可以加工完全部工件。
思路
这个题对于建图是很讲究的,第一眼看上去很有二分图的意思。但是如果你这么建图:一边是0~max(m,n)这些状态(因为无论是两台还是一台,其实都是一样的,因为机器运转的时间是无限的,理论上讲就算只给一个机器,也能完成任务,而且和两台机器所需要的切换次数一样),另一边是0~k这些工件,每一个工件都和他可以被加工的状态连上一条边。
但是这么建图并不能解决问题,首先,只要工件可以在0状态加工,就可以看成不存在了,因为机器无需切换状态就可以加工好,这样,我们在图中所有与0状态相连的点,和0状态本身都要去掉。其次,现在我们规约好的问题已经变成了:在一边的图中选出尽可能少的点,使得这些点的所连接的点可以覆盖对面全部的点。这是典型的“最小支配集”问题。最小支配集问题目前还是NP困难问题。所以此路已经不通了。
我们只好换一种思路,我们发现,如果把一个工件可以加工的两个状态连接起来,建立二分图之后。在这个图上,图的两边分别是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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; int n,m,k; #pragma mark - Hungary Algorithm for BiGraph Matching DFS Version (BGM_H) const int MAXN = 1050; struct Node{ vector<int> to; } X[MAXN],Y[MAXN];//index starts from 0 int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y] bool ap_vis[MAXN];//vis marking array for augment path searching void init(){ for (int i = 0; i < MAXN; i++) { X[i].to.clear(); Y[i].to.clear(); } memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); } int ap_dfs(int u){ for (int i = 0; i < X[u].to.size(); i++) { int v = X[u].to[i]; if (!ap_vis[v]) { ap_vis[v] = true; if (matchY[v] == -1 || ap_dfs(matchY[v])) { matchX[u] = v; matchY[v] = u; return 1; } } } return 0; } int BGM_H(){ int ret = 0; memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); for (int i = 1; i < nx; i++) { if (matchX[i] == -1) { memset(ap_vis, false, sizeof(ap_vis)); if (ap_dfs(i)) { ret++; } } } return ret; } #pragma mark - bool vis[105][105]; int main(){ while (scanf(" %d",&n) != EOF) { if (!n) { break; } memset(vis, 0, sizeof(vis)); scanf(" %d %d",&m,&k); nx = n; ny = k; init(); for (int i = 1; i <= k; i++) { int cur,x,y; scanf(" %d %d %d",&cur,&x,&y); if (x*y != 0 && !vis[x][y]) { X[x].to.push_back(y); vis[x][y] = true; } } cout << BGM_H() << endl;//must not use cerr for output } return 0; } |
September 24, 2015
[…] POJ 2594 Treasure Exploration(允许相交的最小路径覆盖) POJ 1325 Machine Schedule(适当建图,最小点覆盖问题) POJ 1469 COURSES(教学题) HDU 3225 Flowers […]