POJ-3041

思路：将n个行看作n个点{x_i}(i=1, ..., n)，n个列也看作n个点{y_j}(j=1, ..., n)。每个障碍看作一条无向边(x_i, y_j)。则该问题能够归结为求二分图最小点覆盖数，由于最小点覆盖数等于最大匹配数，因此用匈牙利算法求出最大匹配数即可。

算法：

1. 生成两个整数n和m，将网格的规模输入到n，障碍的个数输入到m。

生成一个二维数组g[n][n]，两个一维数组match[n]和chk[n]。
g初始化为全0（g[i][j]==1表示i行j列有一个障碍，g[i][j]==0则表示无障碍）。
match初始化为全0（match[j]==i表示y_j的当前匹配到行x_i，match[j]==0时表示未匹配）。
（chk[j]==0表示y_j未被检查，更确切而言是指在这轮步骤中已被匹配，chk[j]==0则表示已被检查）

生成一个整数ans用于保存结果，初始化为0。

2. 依次将m个障碍的所在行列输入到二维数组g。

3. for i from 1 to n do:
1. chk初始化为全0。

2. 对i行执行下述dfs步骤，若dfs步骤返回成功匹配，则将ans加1：
  （每次返回成功匹配时，match都会更新，否则不变）
      1. for j from 1 to n do:
          若第i行j列存在障碍，并且y_j未被检查，则执行下述步骤：
              1. 设置y_j已被检查。

2. 若第j列是第一次匹配，则设置match[j]=i并返回成功匹配。
若第j列不是第一次匹配，则执行下述步骤：
1. 生成一个整数t，并设置t=match[j]，match[j]=i。

2. 对t行执行dfs步骤，若返回未成功匹配，则将match[j]恢复
为t，否则返回成功匹配。

2. 返回未成功匹配。

4. 输出ans。

#include <iostream>

#include <cstring>

using namespace std;

int n;

int g[][], match[], chk[];

int dfs(int i)

{

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

    {

        if (g[i][j] && !chk[j])

        {

            ++chk[j];

            if (!match[j])

            {

                match[j] = i;

                return ;

            }

            else

            {

                int t = match[j];

                match[j] = i;

                if (!dfs(t))

                {

                    match[j] = t;

                }

                else

                {

                    return ;

                }

            }

        }

    }

    return ;

}

int main()

{

    int m, ans = ;

    cin >> n >> m;

    while (m--)

    {

        int x, y;

        cin >> x >> y;

        ++g[x][y];

    }

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

    {

        memset(chk, 0x00, sizeof(chk));

        ans += dfs(i);

    }

    cout << ans << endl;

    return ;

}

巴特西

POJ-3041

最新文章

热门文章