HDU-1150-MachineSchedule(二分图匹配)

链接：https://vjudge.net/problem/HDU-1150#author=0

题意：

在一个工厂，有两台机器A,
B生产产品。A机器有n种工作模式（模式0,模式1....模式n-1）。

B机器有m种工作模式（模式0,模式1....模式m-1）。
现在要加工k个产品。每个产品可以由两台机器特定的模式生产。
例如：产品0，可以由A机器在3号模式或B机器4号模式生产。

两台机器初始模式都在模式0，但是，这两台机器不是很先进，如果需要切换模式，只能由

人手工切换模式，手工切换可以切换到任意模式。求加工完k个产品需要切换模式的最少次数。

（生产产品的顺序可以任意）

思路：

二分图匹配，尽力从1找到n-1，在右边能找到新的点的情况说明要更改模式。

也就是一条增广路对应一次模式切换。

代码：

#include <iostream>

#include <memory.h>

#include <string>

#include <istream>

#include <sstream>

#include <vector>

#include <stack>

#include <algorithm>

#include <map>

#include <queue>

#include <math.h>

#include <cstdio>

#include <set>

#include <iterator>

#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 1e3+10;

vector<int> G[MAXN];

int Link[MAXN], Vis[MAXN];

int n, m, k;

bool Dfs(int x)

{

    for (int i = 0;i < G[x].size();i++)

    {

        int node = G[x][i];

        if (!Vis[node])

        {

            Vis[node] = 1;

            if (Link[node] == 0 || Dfs(Link[node]))

            {

                Link[node] = x;

                return true;

            }

        }

    }

    return false;

}

int Solve()

{

    int res = 0;

    memset(Link, 0, sizeof(Link));

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

    {

        memset(Vis, 0, sizeof(Vis));

        if (Dfs(i))

            res++;

    }

    return res;

}

void Init()

{

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

        G[i].clear();

}

int main()

{

    while (cin >> n && n)

    {

Init();

        cin >> m >> k;

        int num, l, r;

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

        {

            cin >> num >> l >> r;

            if (l > 0 && r > 0)

                G[l].push_back(r);

        }

        cout << Solve() << endl;

    }

    return 0;

}

巴特西

HDU-1150-MachineSchedule(二分图匹配)

链接：https://vjudge.net/problem/HDU-1150#author=0

题意：

思路：

代码：

最新文章

热门文章