Chinaunix首页 | 论坛 | 博客
  • 博客访问: 474265
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类:

2009-09-26 14:12:41

 

解题思路

题意:

有两台机器AB,分别有n种和m种不同的模式,有k个工作,每个工作都可以在那两个机器的某种特定的模式下处理。如job0既可以在A机器的3好模式下处理,也可以在B机器的4号模式下处理。

机器的工作模式改变只能通过人工来重启。通过改变工作的顺序,和分配每个工作给合适的机器可以减少重启机器的次数达到最小。任务就是计算那个最小的次数。初始时两台机器都运行在0号模式下。

 

思路:

把每个任务化为一条线,假设任务i在A机器上处理的模式为A[x]点,在B机器上为B[y]点,连接A[x]和B[y],用A机器和B机器中最少的点覆盖所有的边(用最少的模式完成所有的任务)。这是最小点覆盖问题,根据König定理(一个二分图中的最大匹配数等于这个图中的最小点覆盖数)就是求的二分图的最大匹配,然后再用匈牙利算法直接就算出最大匹配数了,要注意的是初始是在0号模式下,所以如果AB机器其中至少有个在0号模式下时就不用重启机器了,所以建图的时候没有把0建进去。

 

关于二分匹配在http://blog.chinaunix.net/u3/102624/showart.php?id=2060232

源程序

 

#include <stdio.h>
#include <string.h>
#define N 105
#define M 1005
int g[N][N];
int used[N], mat[N], flag[N];
int min, n, m;

/*寻找增广路径*/
int find(int k)
{
    int i, j;

    for(i=1; i<=g[k][0]; i++)
    {
        j = g[k][i];
        if(!used[j])
        {
            used[j] = 1;
            if(mat[j]==-1 || find(mat[j]))
            {
                mat[j] = k;
                return 1;
            }
        }
    }
    return 0;
}
/*匈牙利算法*/
void hungary()
{
    int i;
    for(i=1; i<=n-1; i++)
    {
        min += find(i);
        memset(used, 0, sizeof(used));
    }
    printf("%d\n", min);
}

int main()
{
    int i, j;
    int k, a, b, c;
    while(scanf("%d", &n) && n)
    {
        scanf("%d%d", &m, &k);
        memset(mat, -1, sizeof(mat));
        memset(g, 0, sizeof(g));  //一开始这个没有初始化,wa了好多次,搞好久 ==!
        for(i=0; i<k; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            if(b != 0 && c != 0)
            {
                g[b][++g[b][0]] = c;    //邻接表
            }
        }
        min = 0;
        hungary();
    }
    return 0;
}


阅读(1200) | 评论(0) | 转发(0) |
0

上一篇:二分匹配

下一篇:poj 1469 courses(二分匹配)

给主人留下些什么吧!~~