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

快来打我* 2022-09-25 08:28 193阅读 0赞

Machine Schedule

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;14308</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;6107</td> 
  </tr> 
 </tbody> 
</table>

Description

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.  
  
There are two machines A and B. Machine A has n kinds of working modes, which is called mode\_0, mode\_1, ..., mode\_n-1, likewise machine B has m kinds of working modes, mode\_0, mode\_1, ... , mode\_m-1. At the beginning they are both work at mode\_0.  
  
For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode\_3 or in machine B at mode\_4, job 1 can either be processed in machine A at mode\_2 or in machine B at mode\_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode\_x, or in machine B at mode\_y.  
  
Obviously, to accomplish all the jobs, we need to change the machine's working mode from time to time, but unfortunately, the machine's working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.

Input

The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.  
  
The input will be terminated by a line containing a single zero.

Output

The output should be one integer per line, which means the minimal times of restarting machine.

Sample Input

5 5 10
    0 1 1
    1 1 2
    2 1 3
    3 1 4
    4 2 1
    5 2 2
    6 2 3
    7 2 4
    8 3 3
    9 4 3
    0

Sample Output

Source

[Beijing 2002][]

## 题目意思： ##

有两台机器A和B，A有N种工作模式0~N-1，B有M 种工作模式0~M-1，刚开始时的初始状态，A和B都在模式0。

给定K个作业，每个作业可以工作在特定的A和B的模式下。样例中，0 1 1 表示作业0可以工作在A的1状态和B的1状态。

为了完成作业，机器必须不断的切换模式，试着写程序实现：改变机器的顺序，给每个作业分配合适的作业，使得重启机器次数最少。

## 解题思路： ##

构造二部图，用匈牙利算法做二分图匹配。

![20160817185800358][]

如果某作业任务可以在A的i状态和B的j状态上完成，则从Ai到Bj连一条边，这样构造二部图。

对于样例来说，选择A状态的1和2，B状态的3。

DFS和BFS效率和内存几乎完全一样…

![20160817190115406][]

## ①DFS ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #define maxn 1010
    #define INF 0xfffffff
    using namespace std;
    int nx,ny;//X与Y集合中元素的个数
    int g[maxn][maxn];//边的邻接矩阵
    int cx[maxn],cy[maxn];//cx[i]表示最终求得的最大匹配中与Xi匹配的顶点，cy[i]同理
    
    int mk[maxn];//mark，记录顶点访问状态
    int path(int u)
    {
        //for(int v=0; v<ny; ++v)//A与B两机器初始为0，所以0状态不必重启，从1开始
        for(int v=1; v<ny; ++v)//考虑Yi的顶点v
            if(g[u][v]&&!mk[v])//v与u邻接，且没有访问过
            {
                mk[v]=1;//访问v
                if(cy[v]==-1||path(cy[v]))//如果v没有匹配，或者v已经匹配但是从cy[v]出发可以找到一条增广路
                {
                    cx[u]=v;//v匹配给u
                    cy[v]=u;//u匹配给v
                    return 1;//找到可增广路
                }
            }
        return 0;//不存在从u出发的增广路
    }
    int MaxMatch()//匈牙利算法
    {
        int res=0;//所求得的最大匹配
        memset(cx,-1,sizeof(cx));//从0开始匹配增广，所以初始化为-1
        memset(cy,-1,sizeof(cy));
        // for(int i=0; i<=nx; ++i)
        for(int i=1; i<=nx; ++i)//A与B两机器初始为0，所以0状态不必重启，从1开始
            if(cx[i]==-1)//从每个未盖点出发进行寻找增广路
            {
                memset(mk,0,sizeof(mk));
                res+=path(i);//每找到一条增广路，可使得匹配数加1
            }
        return res;
    }
    int main()
    {
        int k;
        while(cin>>nx&&nx!=0)
        {
            cin>>ny>>k;
            memset(g,0,sizeof(g));
            int i,a,x,y;
            for(i=0; i<k; ++i)
            {
                cin>>a>>x>>y;
                g[x][y]=1;
            }
            cout<<MaxMatch()<<endl;
        }
        return 0;
    }
    /*
    5 5 10
    0 1 1
    1 1 2
    2 1 3
    3 1 4
    4 2 1
    5 2 2
    6 2 3
    7 2 4
    8 3 3
    9 4 3
    0
    */

## ②BFS ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #define maxn 1010
    #define INF 0xfffffff
    using namespace std;
    int nx,ny;//X与Y集合中元素的个数
    int g[maxn][maxn];//边的邻接矩阵
    int cx[maxn],cy[maxn];//cx[i]表示最终求得的最大匹配中与Xi匹配的顶点，cy[i]同理
    
    int pred[maxn];//用来记录交错轨，同时也记录Y集合中的顶点是否遍历过
    int que[maxn];//数组模拟队列
    int MaxMatch()
    {
        int i,j,y;
        int cur,tail;//队列首位位置的下标
        int res=0;//求得的最大匹配数
        memset(cx,-1,sizeof(cx));//初始化所有点为未被匹配的状态
        memset(cy,-1,sizeof(cy));
        //for(i=0; i<nx; ++i)
        for(i=1; i<nx; ++i)//对X集合中的每个未盖点i进行一次BFS找交错轨
        {
            if(cx[i]!=-1) continue;
            //for(j=0; j<ny; ++j)
            for(j=1; j<ny; ++j)
                pred[j]=-2;//-2是初始值
            cur=tail=0;//初始化队列
            //for(j=0; j<ny; ++j)
            for(j=1; j<ny; ++j)//i的邻接顶点入队列
                if(g[i][j])
                {
                    pred[j]=-1;//-1表示遍历到且是邻接顶点
                    que[tail++]=j;
                }
            while(cur<tail)
            {
                y=que[cur];
                if(cy[y]==-1) break;//找到一个未被匹配的点，则找到了一条交错轨
                ++cur;
                //for(j=0; j<ny; ++j)
                for(j=1; j<ny; ++j)//y已经被匹配给cy[y]了，从cy[y]出发，将它的邻接顶点入队列
                    if(pred[j]==-2&&g[cy[y]][j])
                    {
                        pred[j]=y;
                        que[tail++]=j;
                    }
            }
            if(cur==tail) continue;//没有找到交错轨
            while(pred[y]>-1)//更改交错轨上的匹配状态
            {
                cx[cy[pred[y]]]=y;
                cy[y]=cy[pred[y]];
                y=pred[y];
            }
            cy[y]=i;
            cx[i]=y;
            res++;
        }
        return res;
    }
    int main()
    {
        int k;
        while(cin>>nx&&nx!=0)
        {
            cin>>ny>>k;
            memset(g,0,sizeof(g));
            int i,a,x,y;
            for(i=0; i<k; ++i)
            {
                cin>>a>>x>>y;
                g[x][y]=1;
            }
            cout<<MaxMatch()<<endl;
        }
        return 0;
    }
    /*
    5 5 10
    0 1 1
    1 1 2
    2 1 3
    3 1 4
    4 2 1
    5 2 2
    6 2 3
    7 2 4
    8 3 3
    9 4 3
    0
    */

[Beijing 2002]: http://poj.org/searchproblem?field=source&key=Beijing+2002
[20160817185800358]: /images/20220718/78904f98d73847f297dd7d4b6a778016.png
[20160817190115406]: /images/20220718/13c1dd9c4572493fb3de6ffcc6f98a58.png