链接：

https://vjudge.net/problem/HDU-1045#author=zzuli_contest

题意：

假设我们有一个有直街的广场城市。城市地图是一个方形板，有n行和n列，每列代表一条街道或一块墙。

碉堡是一座小城堡，有四个开口可以射击。四个开口分别面向北，东，南和西。每个开口都会有一挺机枪射击。

在这里，我们假设子弹是如此强大，以至于它可以穿越任何距离并在途中摧毁一个碉堡。另一方面，墙壁结构坚固，可以阻止子弹。

目标是尽可能多地在城市中设置碉堡，这样就不会有两个碉堡相互摧毁。如果没有两个碉堡在地图的同一水平行或垂直列上，除非至少有一个墙将它们分开，否则碉堡的配置是合法的。在这个问题中，我们将考虑小方形城市（最多4x4），其中包含无法穿过子弹的墙壁。

下图显示了同一块板的五张图片。第一张图片是空白板，第二张和第三张图片显示合法配置，第四张和第五张图片显示非法配置。对于该板，合法配置中的最大块仓数为5; 第二张图片显示了一种方法，但还有其他几种方法。

您的任务是编写一个程序，在给定地图描述的情况下，计算可以在合法配置中放置在城市中的最大数量的阻止房屋。

思路：

将一行，通过墙壁被分成几块，行和列相同处理，在进行二分图的最大匹配

代码：

#include <iostream>

#include <cstdio>

#include <vector>

#include <memory.h>

#include <queue>

#include <set>

#include <map>

using namespace std;

const int MAXN = 10;

char Map[MAXN][MAXN];

int DisRow[MAXN][MAXN];

int DisCol[MAXN][MAXN];

int Linked[20], Vis[20];

vector<int> G[MAXN];

int n;

int row, col;

bool Dfs(int x)

{

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

    {

        int nextnode = G[x][i];

        if (Vis[nextnode])

            continue;

        Vis[nextnode] = 1;

        if (Linked[nextnode] == -1 || Dfs(Linked[nextnode]))

        {

            Linked[nextnode] = x;

            return true;

        }

    }

    return false;

}

int Solve()

{

    int cnt = 0;

    memset(Linked, -1, sizeof(Linked));

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

    {

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

        if (Dfs(i))

            cnt++;

    }

    return cnt;

}

int main()

{

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

    {

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

            scanf("%s", Map[i]+1);

        row = col = 0;

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

        {

            bool flag = false;

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

            {

                if (Map[i][j] == '.')

                {

                    if (!flag)

                        DisRow[i][j] = ++row, flag = true;

                    else

                        DisRow[i][j] = row;

                }

                else

                    flag = false;

            }

        }

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

        {

            bool flag = false;

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

            {

                if (Map[j][i] == '.')

                {

                    if (!flag)

                        DisCol[j][i] = ++col, flag = true;

                    else

                        DisCol[j][i] = col;

                }

                else

                    flag = false;

            }

        }

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

            G[i].clear();

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

        {

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

                if (Map[i][j] == '.')

                    G[DisRow[i][j]].push_back(DisCol[i][j]);

        }

        int cnt = Solve();

        cout << cnt << endl;

    }

    return 0;

}

巴特西

HDU-1045-Fire Net（最大匹配）

链接：

题意：

思路：

代码：

最新文章

热门文章