55分求助大佬
查看原帖
55分求助大佬
1098596
2308weibowen楼主2024/9/9 17:18
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 505

struct Maps {
	int num , h;
	Maps (int num = 0 , int h = 0):
		num(num) , h(h) {}
};

const int dx[4] = {1 , 0 , -1 , 0};
const int dy[4] = {0 , 1 , 0 , -1};

int n , m , inp[MAXN*MAXN] , out[MAXN*MAXN] , in , ou;
int dfn[MAXN*MAXN] , low[MAXN*MAXN] , scc[MAXN*MAXN] , scid , visid;
bool is[MAXN*MAXN] , vis[MAXN*MAXN];
stack <int> s;
Maps map[MAXN][MAXN];
vector <int> v[MAXN*MAXN];

void tanjan (int u)
{
	dfn[u] = low[u] = ++ visid;
	is[u] = true , vis[u] = true , s.push(u);
	for(auto i : v[u])
	{
		if(vis[i] == false){
			tanjan (i);
			low[u] = min (low[u] , low[i]);
		}
		else if (is[u])
			low[u] = min (low[u] , dfn[i]);
	}
//	printf ("test in --> u = %d  low[u] = %d  dfn[u] = %d\n",u,low[u],dfn[u]);
	if(low[u] == dfn[u])
	{
		int p;
		++ scid;
		do {
			p = s.top(); s.pop();
			is[p] = false , scc[p] = scid;
		} while (p != u);
	}
}

int main()
{
	scanf("%d%d",&m,&n);
	for(int i = 1 ; i <= n ; i ++)
	{
		for(int j = 1 ; j <= m ; j ++)
		{
			scanf("%d",&map[i][j].h);
			map[i][j].num = (i-1)*m+j;
		}
	}
	
	for(int i = 1 ; i <= n ; i ++)
	{
		for(int j = 1 ; j <= m ; j ++)
		{
			for(int k = 0 ; k < 4 ; k ++)
			{
				int tx = i + dx[k] , ty = j + dy[k];
				if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && map[i][j].h >= map[tx][ty].h)
				{
					v[map[i][j].num].push_back(map[tx][ty].num);
				}
			}
		}
	}
	for(int i = 1 ; i <= n*m ; i ++)
		if(vis[i] == false) tanjan (i);
	
//	cout << "scc[14] = " << scc[14] << '\n';
	
	for(int i = 1 ; i <= n ; i ++)
	{
		for(int j = 1 ; j <= m ; j ++)
		{
			for(auto k : v[map[i][j].num])
			{
//				if(map[i][j].h == 3)
//				{
//					cout << "k == " << k << " scc[k] == " << scc[k] << '\n';
//					cout << int(scc[map[i][j].num] != scc[k]) << '\n';
//				}
				if(scc[map[i][j].num] != scc[k])
				{
					++ inp[scc[k]];
					++ out[scc[map[i][j].num]];
//					printf("ins --> k = {%d %d scc = %d} map[%d][%d] = {%d %d scc = %d} inp[%d] = %d out[%d] = %d\n",k,k.h,scc[k.num],i,j,map[i][j].num,map[i][j].h,scc[map[i][j].num],scc[k.num],inp[scc[k.num]],scc[map[i][j].num],out[scc[map[i][j].num]]);
				}
			}
		}
	}
	
	for(int i = 1 ; i <= scid ; i ++)
	{
		if(inp[i] == 0) ++ in;
		if(out[i] == 0) ++ ou;
	}
	
//	printf ("test --> in = %d   ou = %d\n",in,ou);
	
	cout << max (in , ou) << '\n';
	
	return 0;
}

非常求助,样例没过但55分,怀疑tanjan算法出错或者是枚举时出错,但自己测试查不出错误,谢谢大佬

2024/9/9 17:18
加载中...