BZOJ 4554: [Tjoi2016&Heoi2016]游戏

Description

在2016年,佳缘姐姐喜欢上了一款游戏,叫做泡泡堂。简单的说,这个游戏就是在一张地图上放上若干个炸弹,看是否能炸到对手,或者躲开对手的炸弹。在玩游戏的过程中,小H想到了这样一个问题:当给定一张地图,在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。
炸弹能炸到的范围是该炸弹所在的一行和一列,炸弹的威力可以穿透软石头,但是不能穿透硬石头。给定一张nm的网格地图:其中代表空地,炸弹的威力可以穿透,可以在空地上放置一枚炸弹。x代表软石头,炸弹的威力可以穿透,不能在此放置炸弹。#代表硬石头,炸弹的威力是不能穿透的,不能在此放置炸弹。例如:给出14的网格地图xx,这个地图上最多只能放置一个炸弹。
给出另一个1
4的网格地图x#,这个地图最多能放置两个炸弹。现在小H任意给出一张n*m的网格地图,问你最多能放置多少炸弹

Input<

第一行输入两个正整数n,m,n表示地图的行数,m表示地图的列数。1≤n,m≤50。接下来输入n行m列个字符,代表网格地图。的个数不超过nm个

Output

输出一个整数a,表示最多能放置炸弹的个数

Sample Input

4 4
#***
*#**
**#*
xxx#

Sample Output

5

Solution

二分图匹配

遇到一个#,就把这一行和列从这里断开,遇到一个*,行和列就和普通的一样连一条边。

注意这题Sample Output的星号不对 手动改一波。

Code

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
namespace Dinic {
    struct Edge { int to, next, r; } edge[400010];
    int h[200005], cnte = 1, dis[200005], S, T;
    queue<int> Q;
    void insert(int x, int y, int z) {
        edge[++cnte].to = y;
        edge[cnte].next = h[x];
        edge[cnte].r = z;
        h[x] = cnte;
    }
    void ins(int x, int y, int z) {
        insert(x, y, z);
        insert(y, x, 0);
    }
    int dfs(int x, int a) {
        if (a == 0 || x == T) return a;
        int f, ret = 0;
        for (int i = h[x]; i; i = edge[i].next) {
            if (dis[edge[i].to] == dis[x] + 1) {
                if (f = dfs(edge[i].to, min(edge[i].r, a))) {
                    ret += f;
                    a -= f;
                    edge[i].r -= f;
                    edge[i^1].r += f;
                    if (a == 0) break;
                }
            }
        }
        if (ret == 0) dis[x] = -1;
        return ret;
    }
    bool bfs() {
        for (int i = S; i <= T; ++i) dis[i] = -1;
        dis[S] = 0; Q.push(S);
        int now;
        while (!Q.empty()) {
            now = Q.front(); Q.pop();
            for (int i = h[now]; i; i = edge[i].next) {
                if (edge[i].r && dis[edge[i].to] == -1) {
                    dis[edge[i].to] = dis[now] + 1;
                    Q.push(edge[i].to);
                }
            }
        }
        return dis[T] != -1;
    }
    int go() {
        int flow = 0;
        while (bfs())
            flow += dfs(S, INF);
        return flow;
    }
}
using Dinic::S;
using Dinic::T;
int lid[55][55], hid[55][55], tot, n, m, ans, tmp;
char str[55][55];
int main() {
    //freopen("I:\\input.txt", "r", stdin);
    n = getint(); m = getint();
    for (int i = 1; i <= n; ++i)
        scanf("%s", str[i]+1);
    for (int i = 1; i <= n; ++i) {
        ++tot;
        for (int j = 1; j <= m; ++j) {
            if (str[i][j] == '#') ++tot;
            else hid[i][j] = tot;
        }
    }
    tmp = tot;
    for (int j = 1; j <= m; ++j) {
        ++tot;
        for (int i = 1; i <= n; ++i) {
            if (str[i][j] == '#') ++tot;
            else lid[i][j] = tot;
        }
    }
    S = 0; T = ++tot;
    for (int i = 1; i <= tmp; ++i) Dinic::ins(S, i, 1);
    for (int i = tmp + 1; i < tot; ++i) Dinic::ins(i, T, 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (str[i][j] == '*')
               Dinic::ins(hid[i][j], lid[i][j], 1);
    ans = Dinic::go();
    printf("%d", ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据