[BZOJ4554/Luogu2825][Tjoi2016&Heoi2016]游戏(网络流,二分图)

发布于 2018-02-07  98 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4554/Luogu2825][Tjoi2016&Heoi2016]游戏(网络流,二分图)

Description

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

Http

BZOJ
Luogu

Tag

网络流,二分图

解决思路

若没有硬石头的限制,就是一个比较简单的二分图模型,对于每一行每一列连边求最大匹配即可。
但由于有了硬石头的限制,我们可以把每一行以硬石头为界分成若干块,每一列同理,相当于拆点,再按照二分图模型连边。
这里就用网络流了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxMap=52;
const int maxN=maxMap*maxMap*2;
const int maxM=maxN*20;
const int inf=2147483647;

class Edge
{
public:
    int v,flow;
};

int n,m,S,T;
char Input[maxMap][maxMap];
int Idx[maxMap][maxMap],Idy[maxMap][maxMap];
int nodecnt=0,edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
bool Con[maxN];
int Depth[maxN],Queue[maxN],cur[maxN];

void Add_Edge(int u,int v,int flow);
bool Bfs();
int dfs(int u,int flow);

int main()
{
    mem(Head,-1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%s",Input[i]+1);
    for (int i=1;i<=n;i++)//接下来这两个循环分别把行和列分成若干快
        for (int j=1;j<=m;j++)
        {
            if (Input[i][j]=='#')
            {
                Idx[i][j]=-1;
                continue;
            }
            if ((j==1)||(Input[i][j-1]=='#'))
            {
                Idx[i][j]=++nodecnt;
                continue;
            }
            Idx[i][j]=nodecnt;
        }
    for (int j=1;j<=m;j++)
        for (int i=1;i<=n;i++)
        {
            if (Input[i][j]=='#')
            {
                Idy[i][j]=-1;
                continue;
            }
            if ((i==1)||(Input[i-1][j]=='#'))
            {
                Idy[i][j]=++nodecnt;
                continue;
            }
            Idy[i][j]=nodecnt;
        }
    S=nodecnt+1;T=nodecnt+2;
    for (int i=1;i<=n;i++)//二分图连边
        for (int j=1;j<=m;j++)
        {
            if (Input[i][j]=='#') continue;
            if (Input[i][j]=='*') Add_Edge(Idx[i][j],Idy[i][j],1);
            if (Input[i][j]=='*')
            {
                if (Con[Idx[i][j]]==0)
                {
                    Con[Idx[i][j]]=1;
                    Add_Edge(S,Idx[i][j],1);
                }
                if (Con[Idy[i][j]]==0)
                {
                    Con[Idy[i][j]]=1;
                    Add_Edge(Idy[i][j],T,1);
                }
            }
        }
    int Ans=0;//求解最大流
    while (Bfs())
    {
        for (int i=1;i<=T;i++) cur[i]=Head[i];
        while (int di=dfs(S,inf)) Ans+=di;
    }
    printf("%d\n",Ans);
    return 0;
}

void Add_Edge(int u,int v,int flow)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].v=v;E[edgecnt].flow=flow;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt].v=u;E[edgecnt].flow=0;
    return;
}

bool Bfs()
{
    mem(Depth,-1);
    int h=1,t=0;Queue[1]=S;Depth[S]=1;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((E[i].flow>0)&&(Depth[E[i].v]==-1))
                Depth[Queue[++h]=E[i].v]=Depth[u]+1;
    }
    while (t!=h);
    if (Depth[T]==-1) return 0;
    return 1;
}

int dfs(int u,int flow)
{
    if (u==T) return flow;
    for (int &i=cur[u];i!=-1;i=Next[i])
        if ((E[i].flow>0)&&(Depth[E[i].v]==Depth[u]+1))
        {
            int di=dfs(E[i].v,min(flow,E[i].flow));
            if (di)
            {
                E[i].flow-=di;
                E[i^1].flow+=di;
                return di;
            }
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4554/Luogu2825][Tjoi2016&Heoi2016]游戏(网络流,二分图)


HNCJ OIer 一枚