自动搬运

查看原文

来自洛谷，原作者为

	xiwang **

搬运于2025-08-24 21:59:33，当前版本为作者最后更新于2018-05-09 08:32:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

千亿的STL,千亿的迭代器
第一问好写，每个格子跑floodfill就好了
起初写了个暴力版的，就是直接枚举可能的号码组合然后用第一问结果统计
然后就爆炸了
然后我找到了官方（？）题解，然后那代码在我的破电脑上编译不了
然后我只好对每一组号码组合建一张图
那么怎么搞映射呢？map
重复边怎么去重？用map<int,set >存图
怎么不MLE呢？靠神奇的STL
怎么不TLE呢？O2
所以我们把第一问处理出的每一个联通块缩成一个点，之后针对每一组可能的号码组合（原图中相邻的不同号码）建一张图，map搞搞映射，之后每一张新图暴力统计答案就好了
丑陋的代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=256;
typedef pair<int,int> pii;
#define X first
#define Y second
int n,a[N][N],id[N][N],arid,clk;
struct gph{
  map<int,set<int> > g;
  map<int,int> nsz,rid,rsz;
};
map<int,gph> g1;
map<pii,gph> g2;

int dfs(gph &g,int nid,int rid){
  if(g.rid.count(nid)>0)return 0;
  g.rid[nid]=rid;
  int x=g.nsz[nid];
  for(set<int>::iterator i=g.g[nid].begin();i!=g.g[nid].end();i++){
  	x+=dfs(g,*i,rid);
  }
  g.rsz[rid]=x;
  return x;
}
int fuck(gph &g){
  int re=0;
  for(map<int,set<int> >::iterator i=g.g.begin();i!=g.g.end();i++)re=max(re,dfs(g,(*i).X,++arid));
  return re;
}
void add(gph &g,int st,int ed){
  g.g[st].insert(ed);
  g.g[ed].insert(st);
  g.nsz[st]=g.nsz[ed]=1;
}
void addg2(int x1,int y1,int x2,int y2){
  int c1=a[x1][y1],c2=a[x2][y2],id1=id[x1][y1],id2=id[x2][y2];
  if(c1>c2)swap(c1,c2),swap(id1,id2);
  int r1=g1[c1].rid[id1],r2=g1[c2].rid[id2];
  pii p=pii(c1,c2);
  add(g2[p],r1,r2);
  g2[p].nsz[r1]=g1[c1].rsz[r1];                                                              
  g2[p].nsz[r2]=g1[c2].rsz[r2];  
}
int main(){
  //printf("Dioptic manifold clear.\n");
  scanf("%d",&n);
  for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]),id[i][j]=++clk;
  for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
  	add(g1[a[i][j]],id[i][j],id[i][j]);
  	if(i<n&&a[i+1][j]==a[i][j])add(g1[a[i][j]],id[i][j],id[i+1][j]);
  	if(j<n&&a[i][j+1]==a[i][j])add(g1[a[i][j]],id[i][j],id[i][j+1]);;
  }
  int ass1=0;
  for(map<int,gph>::iterator i=g1.begin();i!=g1.end();i++){
  	ass1=max(ass1,fuck((*i).Y));
  }
  for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
  	if(i<n&&a[i+1][j]!=a[i][j])addg2(i,j,i+1,j);
  	if(j<n&&a[i][j+1]!=a[i][j])addg2(i,j,i,j+1);
  }
  int ass2=0;
  for(map<pii,gph>::iterator i=g2.begin();i!=g2.end();i++){
  	ass2=max(ass2,fuck((*i).Y));
  }
  printf("%d\n%d",ass1,ass2);
  return 0;
}