洛谷P2172 [国家集训队]部落战争 题解

题目链接：https://www.luogu.org/problemnew/show/P2172

分析：

不要被【国家集训队】的标签吓到，其实这题不是很难。

本题可以对比P4304 [TJOI2013]攻击装置：互不攻击的网络流问题来想。

这道题唯一添加的条件就是只能从上往下征战，于是我们就从8个方向缩减到了四个放向，哪四个呢？

aa[1]=r;bb[1]=-c;

aa[2]=r;bb[2]=c;

aa[3]=c;bb[3]=-r;

aa[4]=c;bb[4]=r;

变量名较丑

然后还是要循环每一个点来把它能攻击到的点扔进vector里。

还有这题的数据范围其实也挺小，适合练习二分图初级。

然后就是这种题目也是不用else break；了！

因为不存在单调性

代码：

#include<cstdio>

#include<iostream>

#include<vector>

using namespace std;

int aa[5];

int bb[5];

struct ben

{

	int first,second;

};

vector<ben>v[55][55];

int vis[55][55];

ben link[55][55];

int t;

int a[55][55];

bool find(ben tmp)

{

    int x=tmp.first;

    int y=tmp.second;

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

    {

        int p=v[x][y][i].first;

        int q=v[x][y][i].second;

        if(vis[p][q]!=t)

        {

            vis[p][q]=t;

            int ls=link[p][q].first;

            int ls2=link[p][q].second;

            if((ls==0&&ls2==0)||find(link[p][q]))

            {

                link[p][q].first=x;

                link[p][q].second=y;

                return 1;

            }

        }

    }

    return 0;

}

int main()

{

	int n,m,r,c;

	int ans=0;

	scanf("%d%d%d%d",&m,&n,&r,&c);

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

	{

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

		{

			char s;

			cin>>s;

			if(s=='.')

			{

				a[i][j]=0;

				ans++;

			}

			else

			a[i][j]=1;

		}

	}

	aa[1]=r;bb[1]=-c;

	aa[2]=r;bb[2]=c;

	aa[3]=c;bb[3]=-r;

	aa[4]=c;bb[4]=r;

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

	{

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

		{

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

			{

				int x=i+aa[k];

				int y=j+bb[k];

				if(x>0&&x<=m&&y>0&&y<=n&&a[x][y]==0)

				{

					ben tmp;

					tmp.first=x;

					tmp.second=y;

					v[i][j].push_back(tmp);

				}

			}

		}

	}

	int cnt=0;

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

    {

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

        {

            if(a[i][j]==1)

            continue;

            t++;

            ben tmp;

            tmp.first=i;

            tmp.second=j;

            if(find(tmp))

            {

                cnt++;

            }

            //else

            //break;

        }

    }

    printf("%d\n",t-cnt);

    return 0;

}