【BZOJ 2150】【国家集训队】部落战争 / 题解

BZOJ原题地址

洛谷原题地址

题目描述

lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。

A国是一个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定：

• 每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。

• 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。

• 每支军队都可以在任意一个城镇停止征战。

所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走1×2的路线，而他们只能走R×C的路线。

lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。

输入输出

输入格式

第一行包含4个整数M、N、R、C，意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是’.’，表示这个地方是城镇；如果这个字符时’x’，表示这个地方是高山深涧。

输出格式

输出一个整数，表示最少的军队个数。

思路

我们把军队所在点和他们可以走到的点直接连边，我们就得到了一张二分图。考虑到军队只会向下走，所以这道题可以很容易的被我们转换成二分图匹配中的最小路径覆盖。

一开始每个点都是独立的为一条路径，总共有 n 条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。

所以：最小路径覆盖=结点数-最大匹配数。

使用匈牙利算法解决这个问题。

代码

#include 
#define maxn 2501
#define num(i,j) (i-1)*n+j
using namespace std;
bool edge[maxn][maxn],vis[maxn];
int n,m,r,c,id,qwq=0,path[maxn],ans;
int town[maxn][maxn],dx[4],dy[4];
bool find(int x){
    for (int j=1;j<=id;j++){ if (edge[x][j]&&!vis[j]){ vis[j]="1;" (path[j]="=0||find(path[j])){" path[j]="x;return" 1;}}} return 0; } int main(){ ios::sync_with_stdio(false); cin>>m>>n>>r>>c;char mark;
    for (int i=1;i<=m;i++) for (int j="1;j<=n;j++)" {cin>>mark;if (mark=='.') town[i][j]=1,qwq++;}
    dx[0]=r;dx[1]=r;dx[2]=c;dx[3]=c;
    dy[0]=-c;dy[1]=c;dy[2]=-r;dy[3]=r;id=m*n;
    for (int i=1;i<=m;i++) for (int j="1;j<=n;j++)" if (town[i][j]) k="0;k<=3;k++){" int x="i+dx[k],y=j+dy[k];" (x<1||x>m||y>n) continue;
        if (town[x][y]) edge[num(i,j)][num(x,y)]=1;}
    for (int i=1;i<=m;i++) for (int j="1;j<=n;j++){" memset(vis,0,sizeof(vis)); if (town[i][j]) (find(num(i,j))) ans++;} cout<