题解 P4380 【[USACO18OPEN]Multiplayer Moo】

· · 题解

千亿的STL,千亿的迭代器
第一问好写，每个格子跑floodfill就好了
起初写了个暴力版的，就是直接枚举可能的号码组合然后用第一问结果统计
然后就爆炸了
然后我找到了官方（？）题解，然后那代码在我的破电脑上编译不了
然后我只好对每一组号码组合建一张图
那么怎么搞映射呢？map
重复边怎么去重？用map<int,set<int> >存图
怎么不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;
}