UVALive 2523 Machine Schedule（二分图求最大匹配数）

　　题意：有两台机器，上面有多个工作区域，有多个任务，分别可以在两台机器的某一个区域上完成，两台机器一开始都在0区域上工作，每次更改区域，都会重新启动一次，让我们求出最小的重启次数。

　　思路：将两个区域连线，使用二分图，求出最大匹配数，容易想明白，正好就是最小重启的次数。

　　注意：0一开始就已经完成，不应该加入到匹配序列。

代码如下：

#include<iostream>

#include<algorithm>

#include<queue>

#include<cstdio>

#include<cstring>

using namespace std;

#define N 110

int maps[N][N],n,m,match[N],vis[N];

bool Find(int x)

{

    for(int i = ; i <= m; i++)

    {

        if(maps[x][i] && !vis[i])

        {

            vis[i] = ;

            if(match[i]==-|| Find(match[i]))

            {

                match[i] = x;

                return true;

            }

        }

    }

    return false;

}

int hungry()

{

    memset(match,-,sizeof(match));

    int ans = ;

    for(int i = ; i <= n; i++)

    {

        memset(vis,,sizeof(vis));

        if(Find(i)) ans++;

    }

    return ans;

}

int main()

{

    int a,b,c,k;

    // freopen("G.in.cpp","r",stdin);

    while(~scanf("%d",&n))

    {

        if(!n) break;

        scanf("%d%d",&m,&k);

        memset(maps,,sizeof(maps));

        for(int i = ; i < k; i++)

        {

            scanf("%d%d%d",&a,&b,&c);

            if(b> && c>)

                maps[b][c] = ;

        }

        printf("%d\n",hungry());

    }

    return ;

}

UVALive 2523 Machine Schedule（二分图求最大匹配数）的相关教程结束。