可撤销并查集又T又WA,求调
  • 板块学术版
  • 楼主czy0323
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/30 12:01
  • 上次更新2023/11/3 00:22:27
查看原帖
可撤销并查集又T又WA,求调
538427
czy0323楼主2023/8/30 12:01
#include <bits/stdc++.h>
using namespace std;
const int N = 705;
int n, cnt;
int fa[N * N], siz[N * N];
int h[N][N], v[N][N];
int fx[2][2] = {{0, 1}, {1, 0}};

inline int find(int now){
	if( fa[now] == now )
		return now;
	return find(fa[now]);
}

struct line{
	double data;
	int u, v;
	bool operator <(const line &b) const{
		return data < b.data;
	}
} edge[N * N * 4];

stack<pair<int, int>> s;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cin >> h[i][j];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cin >> v[i][j];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++){
			fa[(i - 1) * n + j] = (i - 1) * n + j;
			siz[(i - 1) * n + j] = 1;
		}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 0; k < 2; k++){
				int xx = i + fx[k][0], yy = j + fx[k][1];
				if( xx < 1 || xx > n || yy < 1 || yy > n )
					continue;
				if( v[i][j] == v[xx][yy] ){
					if( h[i][j] == h[xx][yy] ){
						int fax = find((i - 1) * n + j), fay = find((xx - 1) * n + yy);
						if( siz[fax] > siz[fay] ){
							siz[fax] += siz[fay];
							fa[fay] = fax;
						}
						else{
							siz[fay] += siz[fax];
							fa[fax] = fay;
						}
					}
				}
				else{
					double d = (h[xx][yy] - h[i][j]) * 1.0 / (v[i][j] - v[xx][yy]);
					if( h[i][j] != h[xx][yy] && d > 0 ){
						++cnt;
						edge[cnt].data = d, edge[cnt].u = (i - 1) * n + j, edge[cnt].v = (xx - 1) * n + yy;
					}
				}
			}
		}
	}
	sort(edge + 1, edge + 1 + cnt);
	
	int last = 1, ans = 0;
	while( last <= cnt ){
		int now = last;
		while( now <= cnt && fabs(edge[last].data - edge[now].data) < 1e-6 )
			now++;
		now--;
		for(int i = last; i <= now; i++){
			int fax = find(edge[i].u), fay = find(edge[i].v);
			if( fax == fay )	continue;
			if( siz[fax] > siz[fay] ){
				siz[fax] += siz[fay];
				fa[fay] = fax;
				s.push({fax, fay});
			}
			else{
				siz[fay] += siz[fax];
				fa[fax] = fay;
				s.push({fay, fax});
			}
		}
		for(int i = last; i <= now; i++)
			ans = max(ans, siz[find(edge[i].u)]);
		while( !s.empty() ){
			pair<int, int> h = s.top();
			s.pop();
			siz[h.first] -= siz[h.second];
			fa[h.second] = h.second;
		}
		last = now + 1;
	}
	cout << ans;
	return 0;
}
2023/8/30 12:01
加载中...