求助，普及模考 D3T3

问题讨论区 普及段
1 
#include <algorithm>
#include <cstdio>
#include <queue>
#include <set>
#include <utility>
#include <vector>

const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n, m, idx;
std::vector <std::vector <int>> map, vis, dp[2];

void bfs(int x, int y);

int main(void)
{
	// freopen("C.in", "r", stdin);
	// freopen("C.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	map = std::vector <std::vector <int>>(n + 1, std::vector <int>(m + 1));
	dp[0] = std::vector <std::vector <int>>(n + 1, std::vector <int>(m + 1));
	dp[1] = std::vector <std::vector <int>>(n + 1, std::vector <int>(m + 1));
	vis = std::vector <std::vector <int>>(n + 1, std::vector <int>(m + 1));
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] <= 0 || vis[i][j])
			{
				continue;
			}
			
			idx++;
			
			bfs(i, j);
		}
	}
	
	int ans = 0;
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] == -1)
			{
				std::set <int> s;
				int res = 0;
				
				for (int k = 0; k < 4; k++)
				{
					int tx = i + dir[k][0], ty = j + dir[k][1];
					
					if (1 <= tx && tx <= n && 1 <= ty && ty <= m && s.find(dp[1][tx][ty]) == s.end())
					{
						res += dp[0][tx][ty];
						s.insert(dp[1][tx][ty]);
					}
				}
				
				ans = std::max(ans, res);
			}
		}
	}
	
	printf("%d", ans);
	return 0;
}

void bfs(int x, int y)
{
	int ans = 0;
	std::queue <std::pair <int, int>> q;
	q.push(std::make_pair(x, y));
	
	while (!q.empty())
	{
		std::pair <int, int> f = q.front();
		q.pop();
		
		ans += map[f.first][f.second];
		
		for (int i = 0; i < 4; i++)
		{
			int tx = f.first + dir[i][0], ty = f.second + dir[i][1];
			
			if (1 <= tx && tx <= n && 1 <= ty && ty <= m && !vis[tx][ty] && map[tx][ty] != -1)
			{
				q.push(std::make_pair(tx, ty));
				vis[tx][ty] = idx;
			}
		}
	}
	
	q.push(std::make_pair(x, y));
	dp[0][x][y] = ans;
	dp[1][x][y] = idx;
	
	while (!q.empty())
	{
		std::pair <int, int> f = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++)
		{
			int tx = f.first + dir[i][0], ty = f.second + dir[i][1];
			
			if (1 <= tx && tx <= n && 1 <= ty && ty <= m && vis[tx][ty] == idx && map[tx][ty] != -1 && dp[1][tx][ty] <= 0)
			{
				dp[0][tx][ty] = ans;
				dp[1][tx][ty] = idx;
				q.push(std::make_pair(tx, ty));
			}
		}
	}
}

不知道为什么，第一个样例是好的，第二个样例莫名其妙的多了一，交上去爆零。

2

题面是什么

3

image
image958×2236 219 KB

4

awa你的bfs中没有对起始位置作标记

5 
void bfs(int x, int y)
{
	int ans = 0;
	std::queue <std::pair <int, int>> q;
	q.push(std::make_pair(x, y));
    //---------------------
	vis[x][y] = true;
    //---------------------
	while (!q.empty())
	{
		std::pair <int, int> f = q.front();
		q.pop();
		
		ans += map[f.first][f.second];
		for (int i = 0; i < 4; i++)
		{
			int tx = f.first + dir[i][0], ty = f.second + dir[i][1];
			
			if (1 <= tx && tx <= n && 1 <= ty && ty <= m && !vis[tx][ty] && map[tx][ty] != -1)
			{
				q.push(std::make_pair(tx, ty));
				vis[tx][ty] = idx;
			}
		}
	}
	q.push(std::make_pair(x, y));
	dp[0][x][y] = ans;
	dp[1][x][y] = idx;
	
	while (!q.empty())
	{
		std::pair <int, int> f = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++)
		{
			int tx = f.first + dir[i][0], ty = f.second + dir[i][1];
			
			if (1 <= tx && tx <= n && 1 <= ty && ty <= m && vis[tx][ty] == idx && map[tx][ty] != -1 && dp[1][tx][ty] <= 0)
			{
				dp[0][tx][ty] = ans;
				dp[1][tx][ty] = idx;
				q.push(std::make_pair(tx, ty));
			}
		}
	}
}

加上去样例就能过