题解：P17485 湖上的前线基地 wuxiyi

fish_love_cat · 2026-09-25 18:27:31 · 题解

因为饭堂假了两版，成功糖飞自己。

首先一个观察是一定存在一种方案使得所有连边 (x,y) 均满足 x\in y 或者反过来。证明直接反证一下，分类讨论 x,y 以及 x\operatorname{and} y 的几个连边情况就可以了，容易发现转化为这个是不劣的。

简化边集变成每个点往超集去连，边权是这个点的点权。

考虑 kruskal，给点排个序然后每个点枚举超集，直接做复杂度搞到 O(3^n)。

把枚举超集换成 bfs，于是每个点只会遍历到一次，边的数量是 O(2^nn)，于是时间复杂度就降成了这个东西。

做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct fish{
    int id,x;
}a[(1<<20)+5];
bool cmp(fish x,fish y){
    return x.x<y.x;
}
int fa[(1<<20)+5];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
bool vis[(1<<20)+5];
signed main(){
    int n;
    cin>>n;
    cout<<(1<<n)-1<<'\n';
    for(int i=0;i<(1<<n);i++)
    cin>>a[i].x,a[i].id=i,fa[i]=i;
    sort(a,a+(1<<n),cmp);
    int ans=0;
    for(int i=0;i<(1<<n);i++){
        queue<int>q;
        if(vis[a[i].id])continue;
        q.push(a[i].id);
        vis[a[i].id]=1;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int j=0;j<n;j++)
            if(!(x&(1<<j))){
                int nx=x|(1<<j);
                if(find(nx)==find(x))continue;
                fa[find(x)]=find(nx);
                ans+=a[i].x;
                cout<<a[i].id<<' '<<nx<<'\n';
                if(!vis[nx])q.push(nx);
                vis[nx]=1;
            }
        }
    }
    cout<<ans;
    return 0;
}
// Wuszii /wuˈʂiːː/ wuxiyi