首页 > 代码库 > poj 1325 Machine Schedule 解题报告

poj 1325 Machine Schedule 解题报告

2024-07-18 01:06:56   238人阅读

题目链接：http://poj.org/problem?id=1325

题目意思：有 k 个作业，机器A有 n 个模式：0 ~ n-1，机器B 有 m 个模式：0~ m-1。每一个作业能运行在 A 的 某一个模式（假设为 i (0 <= i <= n-1 ) ）或 B 的某一个模式下(j （0 <= j <= m-1）)。多个作业可以同时运行在 A 的某一个 模式下，当然 B 也如此。每对A 或 B 转换一次模式，就要重启一次 A 或者 B，你需要选择A 或 B 的一些模式，使得所有 k 个 作业能够在最少重启次数下完成。

      这题巧妙之处在于转化问题！题目说，所有 作业 都可以完成的，那么就不关 k 事了。某一个作业在 Ai 或者 Bj 模式下能够被完成，那么就在 Ai 和 Bj 这两点连一条边（map[Ai][Bj] =  1，注意先后顺序），那么问题就转化为 对于机器 A 所有的模式，找到 能与之匹配的 B 的 模式的最大匹配数。

      其实这个是最小点覆盖问题啦，不过因为 最小点覆盖数 == 最大匹配数，所以继续匈牙利算法啦 ，网上很多证明，眼花缭乱，似懂非懂= =

     不过确实转化得好巧妙~~~~~

     

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxk = 1000 + 5; 7  8 int vis[maxk], match[maxk]; 9 int map[maxk][maxk];10 int n, m, k, cnt;11 12 int dfs(int x)13 {14     for (int i = 1; i <= m; i++)15     {16         if (!vis[i] && map[x][i])17         {18             vis[i] = 1;19             if (!match[i] || dfs(match[i]))20             {21                 match[i] = x;22                 return 1;23             }24         }25     }26     return 0;27 }28 29 void Hungary()30 {31     cnt = 0;32     for (int i = 1; i <= n; i++)   // 在 Ai 个模式下，找出对应的Bj，即match[Bj] = Ai33     {34         memset(vis, 0, sizeof(vis));35         cnt += dfs(i);36     }37 }38 39 int main()40 {41     while (scanf("%d", &n) != EOF && n)42     {43         scanf("%d%d", &m, &k);44         int id, x, y;45         memset(match, 0, sizeof(match));46         memset(map, 0, sizeof(map));47 48         for (int i = 1; i <= k; i++)49         {50             scanf("%d%d%d", &id, &x, &y);51             map[x][y] = 1;52         }53         Hungary();54         printf("%d\n", cnt);55     }56     return 0;57 }

 

    


联系
我们