tyvj2054 [Nescafé29]四叶草魔杖

题意

一个有点权和边权的无向图，求 所有点权和为 $0$ 的子图 的最小生成树的权值和。

其中点数 $N\le 16$ 。

题解

看了半天题才得到上面的题意，看到 $N\le 16$ ，显然是状压。

用 $f[id]$ 表示当前点集状态为 $id$ 时的最优解，当 $i$ 和 $j$ 状态内的点权和为 $0$ 时，转移方程式很显然：

$$f[i|j]=f[i]+\text{Kruskal}(j)$$

对每个状态做 $\text{Kruskal}$ 时，可以先处理出包含的点，在所有边中只选择两端都是包含的点的边进行合并。需要注意可能有不连通的情况，也就是说最小生成树做不完，这时返回 $inf$ 。

对于求状态中点权和以及 $\text{Kruskal}$ 的结果可以进行记忆化。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int st,ed,w;
} edge[505];
bool have[20];
int cnt,head[20],n,m,N,v[65536],f[65536],s[20],fa[20],sum[65536];

inline void init() { for (int i=1;i<=n;i++) fa[i]=i; }

int getfa(int x) { return (x==fa[x]) ? x : fa[x]=getfa(fa[x]); }

inline bool merge(int x,int y)
{
    int gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    return fa[gfx]=gfy,1;
}

inline int kruskal(int id)
{
    int cnt=0,&ans=v[id];
    if (ans!=-1) return ans;
    ans=0;
    memset(have,0,sizeof(have));
    for (int i=1;i<=n;i++)
    {
        if (!((1<<(i-1))&id)) continue;
        have[i]=1;
        cnt++;
    }
    init();
    cnt--;
    for (int i=1;i<=m;i++)
    {
        int x=edge[i].st,y=edge[i].ed,w=edge[i].w;
        if (!have[x] || !have[y]) continue;
        if (!merge(x,y)) continue;
        ans+=w;
        cnt--;
        if (!cnt) break;
    }
    if (cnt) ans=inf;
    return ans;
}

inline int get_sum(int id)
{
    int &ans=sum[id];
    if (ans!=-1) return ans;
    ans=0;
    for (int i=1;i<=n;i++)
    {
        if (!((1<<(i-1))&id)) continue;
        ans+=s[i];
    }
    return ans;
}

inline bool cmp(Edge x,Edge y) { return x.w<y.w; }

int main()
{
    n=read(); m=read();
    N=1<<n;
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<=m;i++) edge[i].st=read()+1,edge[i].ed=read()+1,edge[i].w=read();
    sort(edge+1,edge+m+1,cmp);
    memset(v,-1,sizeof(v));
    memset(sum,-1,sizeof(sum));
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for (int i=0;i<N;i++)
    {
        if (get_sum(i)) continue;
        for (int j=1;j<N;j++)
        {
            if (get_sum(j)) continue;
            f[i|j]=min(f[i|j],f[i]+kruskal(j));
        }
    }
    return !printf(f[N-1]>=inf ? "Impossible" : "%d",f[N-1]);
}