题解：P2492 [SDOI2011] 火星移民

C1942huangjiaxu · 2024-04-12 22:05:53 · 题解

连通性问题自然考虑插头 DP。

先有个简单的想法，按照输入顺序依次加入三角形，每次记录还有边没被考虑过的三角形的连通情况，最多 2n 个，按照最小字典序标号，3 个起点的连通块单独记录，为了统计答案，将 3 个终点的连通情况也记录下来。

可以用 16 进制数来表示状态，但是这样总状态数太多了。

考虑到我们记录了所有树的状态，但实际上我们只要记录链的状态。

考虑记录每条链的端点，链中间的点用 0 来表示。

注意到最优解起点和终点会恰好连 1 条边，其余点连 0 或 2 条边，所以我们要在连边时保证这个条件，不然状态数还是会超。

发现考虑到第 i 个点时，连通块连出去的边，只有 i 和 i+1 这条是横向边，其余边都是纵向边。

所以我们可以在之前的状态中，单独记录 i 和 i+1 这条边选不选，这样我们就能保证每个点只连 0 或 2 条边。

保证了之后状态数就不多了，可以通过。

上述方法仅供参考，可能存在更简洁的表示方法。

参考代码加了一些可有可无的剪枝，可读性可能较差。

参考代码（主体部分）：

typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=225,P=1e9+7,Hs=3e6+17,M=1e6+5;
int n,m,a[N],ln[25],vis[4],mx[N],nw,ls,co[N],fa[25],nc[25],sz[25],l1,l2,e[N],E[N];
vector<int>p[N];
pii w[M][2];
int hd[Hs][2],num[2],nx[M][2];
ull to[M][2];
bool vs[25],lc[N],g[N];
inline int md(int x){
    return x>=P?x-P:x;
}
inline pii operator +(pii a,pii b){
    pii c;
    c.first=min(a.first,b.first),c.second=0;
    if(a.first==c.first)c.second=md(c.second+a.second);
    if(b.first==c.first)c.second=md(c.second+b.second);
    return c;
}
void add(int x,int y){
    if(a[x]==4||a[y]==4)return;
    if(x!=y+1)e[x]=y,E[y]=x;
    else g[x]=true;
    mx[y]=max(mx[y],x);
}
inline void ins(ull S,pii v){
    int o=S%Hs;
    for(int i=hd[o][nw];i;i=nx[i][nw])if(to[i][nw]==S){
        w[i][nw]=w[i][nw]+v;
        return;
    }
    nx[++num[nw]][nw]=hd[o][nw],hd[o][nw]=num[nw];
    to[num[nw]][nw]=S,w[num[nw]][nw]=v;
}
inline void chg(int id,ull S,pii v,int o,int e0=0,int e1=0){
    S>>=1;
    v.first+=(e0>0)+(e1>0);
    for(int i=1;i<=12;++i)fa[i]=i,vs[i]=false,sz[i]=0;
    for(int i=0;i<l1;++i)co[p[id-1][i]]=S>>(4*i)&15,++sz[co[p[id-1][i]]];
    if(e[id]&&co[e[id]]&&!lc[e[id]]&&e0!=e[id]&&e1!=e[id])return;
    int &c=co[id];
    c=12;
    if(a[id]&&!vis[a[id]])c=a[id];
    ++sz[c];
    if(!a[id]&&!o&&!e0)c=0;
    if(e0&&!e1){
        int &u=co[e0];
        if(!u)return;
        if(c<4){
            fa[u]=c,c=0;
            if(sz[u]>1)u=0;
        }else{
            c=u;
            if(u<4||sz[u]>1)u=0;
        }
    }else if(e1){
        if(co[e0]>co[e1])swap(e0,e1);
        int &x=co[e0],&y=co[e1];
        co[id]=0;
        if(!x||x==y)return;
        if(y<4)return;
        fa[y]=x;
        if(x<4){
            x=0;
            if(sz[y]>1)y=0;
        }else{
            if(sz[x]>1)x=0;
            if(sz[y]>1)y=0;
        }
    }
    for(int i=0;i<l2;++i){
        int t=p[id][i],c=co[t];
        if(!lc[t])continue;
        if(!c)return;
        if(fa[c]<4&&fa[c]!=a[t])return;
        if(mx[t]<=id&&fa[c]!=a[t]){
            bool fg=false;
            if(id==m)return;
            for(auto z:p[id])if(!lc[z]&&fa[co[z]]==fa[co[t]]){
                fg=true;
                break;
            }
            if(!fg)return;
        }
    }
    ull T=0;
    for(int i=0,ct=4;i<l2;++i){
        int t=p[id][i];
        if(!co[t])continue;
        int u=fa[co[t]];
        if(u<4){
            T|=ull(u)<<(i*4);
            vs[u]=true;
            continue;
        }
        if(!vs[u])vs[u]=true,nc[u]=ct++;
        T|=ull(nc[u])<<(i*4);
    }
    for(int i=1;i<4;++i)if(vis[i]==1&&!vs[i])return;
    ins(T<<1|o,v);
}
void solve(){
    m=6*n*n,num[0]=num[1]=0;
    memset(vis,false,sizeof(vis));
    memset(hd,0,sizeof(hd));
    for(int i=1;i<=m;++i)e[i]=g[i]=E[i]=mx[i]=lc[i]=0;
    for(int i=1;i<=2*n;++i){
        if(i<=n)ln[i]=2*n+2*i-1;
        else ln[i]=2*n+2*(2*n-i)+1;
    }
    for(int i=1,id=0;i<=2*n;++i){
        for(int j=1;j<=ln[i];++j){
            ++id;
            scanf("%d",&a[id]);
            if(a[id]&&a[id]!=4){
                if(vis[a[id]])lc[id]=true;
                vis[a[id]]=true;
            }
            if(j>1)add(id,id-1);
            if((i<=n)!=(j&1)){
                if(i>1){
                    if(i<=n)add(id,id-ln[i]+1);
                    if(i==n+1)add(id,id-ln[i]);
                    if(i>n+1)add(id,id-ln[i]-1);
                }
            }
        }
    }
    for(int i=0;i<=m;++i){
        p[i].clear();
        for(int j=1;j<=i;++j)if(mx[j]>i||lc[j])p[i].push_back(j);
    }
    memset(vis,false,sizeof(vis));
    nw=0,ls=1;
    ins(0,{0,1});
    for(int i=1;i<=m;++i){
        l1=p[i-1].size(),l2=p[i].size();
        swap(nw,ls),num[nw]=0;
        if(a[i]==4)a[i]=0;
        for(int j=1;j<=num[ls];++j){
            ull S=to[j][ls];pii v=w[j][ls];
            hd[S%Hs][ls]=0;
            if(!(S&1)){
                if(a[i]){
                    if(g[i+1])chg(i,S,v,1);
                    if(e[i])chg(i,S,v,0,e[i]);
                    if(E[i])chg(i,S,v,0);
                }else{
                    chg(i,S,v,0);
                    if(g[i+1]&&e[i])chg(i,S,v,1,e[i]);
                    if(g[i+1]&&E[i])chg(i,S,v,1);
                }
            }else{
                if(a[i]){
                    chg(i,S,v,0,i-1);
                }else{
                    if(g[i+1])chg(i,S,v,1,i-1);
                    if(e[i])chg(i,S,v,0,i-1,e[i]);
                    if(E[i])chg(i,S,v,0,i-1);
                }
            }
        }
        ++vis[a[i]];
    }
    if(!num[nw]){
        puts("-1 -1");
        return;
    }
    pii ans={100000,0};
    for(int i=1;i<=num[nw];++i)ans=ans+w[i][nw];
    printf("%d %d\n",ans.first,ans.second);
}