蓝桥杯2019 估计人数

蓝桥杯2019 估计人数

题目描述

给定一个 \(N \times M\) 的方格矩阵，矩阵中每个方格标记 0 或者 1 代表这个方格是不是有人踩过。

已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 1，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。

请你计算至少有多少人在矩阵上走过。

输入格式

输入第一行包含两个整数 \(N\)、\(M\)。
以下 \(N\) 行每行包含一个长度为 \(M\) 的 01 串，代表方格矩阵。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

5 5
00100
11111
00100
11111
00100

样例输出 #1

3

提示

对于所有评测用例, \(1 \leq N, M \leq 20\), 标记为 1 的方格不超过 \(200\) 个。

蓝桥杯 2019 年国赛 A 组 G 题（C 组 H 题）。

解法

此题为可重复的最小路径覆盖问题。
首先先来了解一下什么是不可重复最小路径覆盖问题。

不可重复路径覆盖问题
此问题是指，在一个有向无环图上用最少几条不相交的路径可以将所有的点都覆盖住。
通常的解法是二分图匹配，可以用匈牙利法实现或者用网络流实现。
将图中所有的点拆分成两个，点A拆成点\(A_1 , A_2\)，如果图中有边<u , v>，那么就连接\(<u_1 , v_2>\)，然后求得此图的最大匹配，点数n-最大匹配就是答案。
原因是，将每个点都看作一条长度为0的路径，拆分之后的点看作是路径的首部和尾部，那么二分图上的一次匹配就是将两条路径首尾相接，连接到一起。
所以最大匹配数就是可以省去的路径数。
可重复路径覆盖问题
如果将路径不可交改为路径可交，那么只需要将“原图中<u , v>有边则连接”改为“原图中<u,v>可达则连接”。
可以理解为跳过了路径重叠的部分。

#include<bits/stdc++.h>
using namespace std;
int n , m;
int Match[810] , Visit[810] , Map[810][810];
char String[30][30];

inline int ID(int a , int b , int k) { return (a - 1) * m + b + n * m * k; }

int Dfs(int x)
{
	for(int i = 1 ; i <= n * m ; ++i)
	{
		if(Map[x][i + n * m] && !Visit[i + n * m])
		{
			Visit[i + n * m] = 1;
			if(!Match[i + n * m] || Dfs(Match[i + n * m]))
			{
				Match[i + n * m] = x;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	cin >> n >> m;
	for(int i = 1 ; i <= n ; ++i)
		cin >> (String[i] + 1);
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
			if(String[i][j] == '1')
			{
				int a , b;
				a = i + 1; b = j;
				if(a < 1 || b < 1 || a > n || b > m || String[a][b] == '0');
				else
					Map[ID(i , j , 0)][ID(a , b , 1)] = 1;
				a = i; b = j + 1;
				if(a < 1 || b < 1 || a > n || b > m || String[a][b] == '0');
				else
					Map[ID(i , j , 0)][ID(a , b , 1)] = 1;	
			}
	for(int a = 1 ; a <= n ; ++a) for(int b = 1 ; b <= m ; ++b) if(String[a][b] == '1')
		for(int c = 1 ; c <= n ; ++c) for(int d = 1 ; d <= m ; ++d) if(String[c][d] == '1')
			if(!Map[ID(a , b , 0)][ID(c , d , 1)])
			{
				for(int s = 1 ; s <= n ; ++s) for(int t = 1 ; t <= m ; ++t)
					if(String[s][t] == '1' && Map[ID(a , b , 0)][ID(s , t , 1)] && Map[ID(s , t , 0)][ID(c , d , 1)])
					{
						Map[ID(a , b , 0)][ID(c , d , 1)] = 1;
						goto bk;
					}
				bk:;
			}
	// cout << Map[ID(2 , 3 , 0)][ID(1 , 3 , 1)] << '\n';
	int Answer = 0;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j) if(String[i][j] == '1')
		{
			for(int a = 1 ; a <= n ; ++a)
				for(int b = 1 ; b <= m ; ++b)
					Visit[ID(a , b , 1)] = 0;
			if(!Dfs(ID(i , j , 0))) Answer++;
		}
	cout << Answer << '\n';
	return 0;
}