题解：P10949 四叶草魔杖

· · 题解

题目传送门。

紫题认真的吗？

思路

对于一个点集 S，要让它能量归零当且仅当这个点集的 a_i 和为 0，最小代价显然是该点集导出子图的最小生成树边权之和，容易发现最终选择的边一定是由若干个最小生成树拼凑而成的，再结合数据范围，我们可以直接上子集 DP，时间复杂度 \mathcal O(2^nn^2\log m+3^n)。

可以用子集 exp 优化到 \mathcal O(2^nn^2\log m+2^nn^2)，不过没什么必要。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

const int Maxn=110;
const ll inf=1e15;
int n,m;
int a[Maxn];
int G[Maxn][Maxn];
ll g[1<<16|5];

struct edg{
    int u,v,w;
}E[Maxn];
int tot,f[Maxn];

int qfind(int key){
    return f[key]==key?key:f[key]=qfind(f[key]);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    memset(G,-1,sizeof G);
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G[u][v]=w;
    }
    for(int i=0;i<(1<<n);i++){
        tot=0; ll sm=0;
        for(int j=0;j<n;j++) f[j]=j;
        for(int j=0;j<n;j++) if(i>>j&1) sm+=a[j];
        if(sm!=0){
            g[i]=inf;
            continue;
        }
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                if(G[j][k]!=-1 and i>>j&1 and i>>k&1)
                    E[++tot]=(edg){j,k,G[j][k]};
        sort(E+1,E+tot+1,[](edg x,edg y){
            return x.w<y.w;
        });
        ll ret=0; int cnt=0;
        for(int j=1;j<=tot;j++){
            int u=qfind(E[j].u),v=qfind(E[j].v);
            if(qfind(u)!=qfind(v)){
                f[v]=u; ++cnt;
                ret+=E[j].w;
            }
        }
        int p=__builtin_popcount(i); 

        if(cnt==p-1) g[i]=ret; else g[i]=inf;
    }
    for(int i=0;i<(1<<n);i++)
        for(int j=i;j;j=i&(j-1))
            g[i]=min(g[i],g[i^j]+g[j]);

    ll ans=g[(1<<n)-1];
    if(ans==inf){
        puts("Impossible");
        return 0;
    }
    printf("%lld",ans);

    return 0;
}