2023-07-26 14:35:10 solution

思路

第一眼看以为是个图论，结果发现缩点之后就是个多重背包裸题。

我们把原连通块变成一个重量为连通块大小的物体，然后发现只需要找在容量为幸运数的情况下，放满容量所选物体数量的最小值。

考虑背包，但是复杂度为 \(O(n^2)\)，观察到这题有根号性质，也就是把重量相同的物体缩在一起后总数量不会超过 \(\sqrt n\)，然后做一个二进制优化对多重背包即可，总复杂度 \(O(n\sqrt n \log n)\)。

\(Code\)

unordered_map<int,int>M;
int n,m,fa[100005],siz[100005],w[100005],v[100005],tot,f[100005];
bool  pd[100005];
inline int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
    int xx=find(x),yy=find(y);
    if(xx==yy)return;
    if(siz[xx]>siz[yy])xx^=yy^=xx^=yy;
    siz[yy]+=siz[xx],siz[xx]=0;
    fa[xx]=yy;
}
bool is(int x){
    while(x){
        if(x%10!=4&&x%10!=7)return 0;
        x/=10;
    }
    return 1;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        merge(u,v);
    }
    for(int i=1;i<=n;i++){
        if(pd[find(i)])continue;
        pd[fa[i]]=1;
        M[siz[fa[i]]]++;
    }
    for(auto PI:M){
        int W=PI.first,S=PI.second;
        for(int k=__lg(S)-1;S&&~k;--k){
            if(S>=(1<<k))w[++tot]=W*(1<<k),v[tot]=(1<<k),S-=(1<<k);
        }
        if(S)w[++tot]=W*S,v[tot]=S;
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=tot;i++){
        for(int j=n;j>=w[i];--j){
            f[j]=min(f[j],f[j-w[i]]+v[i]);
        }
    }
    int ans=1e9;
    for(int i=4;i<=n;i++){
        if(is(i)){
            ans=min(ans,f[i]-1);
        }
    }
    if(ans>n)ans=-1;
    cout<<ans;
}