tyvj2054 四叶草魔杖——连通块 & 状压DP

题目：http://www.joyoi.cn/problem/tyvj-2054

把点分成几个连通块，和为0的几个点放在一块，在块内跑最小生成树作为这个块的代价；

然后状压DP，组成全集的最小代价就是答案；

1A了好高兴！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,a[],hd[],ct,f[<<],cnt,fa[],inf=0x3f3f3f3f,g[<<],tot;

bool vis[];

struct N{

    int u,v,w;

    N(int t=,int n=,int w=):u(t),v(n),w(w) {}

}e[];

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

int calc(int g)

{

    int sum=;

    for(int i=;i<=n;i++) if(g&(<<(i-)))sum+=a[i];

    return sum;

}

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

int kruskal(int g)

{

    int num=,ret=;

    memset(vis,,sizeof vis);

    for(int i=;i<=n;i++)

    {

        fa[i]=i;

        if(g&(<<(i-)))vis[i]=,num++;

    }

    int t=;

    for(int i=;i<=m;i++)

    {

        if(!vis[e[i].u]||!vis[e[i].v])continue;

        int u=find(e[i].u),v=find(e[i].v);

        if(u!=v)

        {

            fa[u]=v; ret+=e[i].w; t++;

            if(t==num-)break;

        }

    }

    if(t!=num-)return inf;

    return ret;

}

int main()

{

    scanf("%d%d",&n,&m);

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

    for(int i=;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),e[i].u++,e[i].v++;

    sort(e+,e+m+,cmp);

    memset(f,0x3f,sizeof f);

    for(int i=;i<=(<<n)-;i++)

        if(calc(i)==)

        {

            int ff=kruskal(i);

            if(ff!=inf)g[++tot]=i,f[i]=ff;

        }

    f[]=;

    for(int i=;i<=(<<n)-;i++)

    {

        for(int j=;j<=tot;j++)

            if((i&g[j])==)f[i|g[j]]=min(f[i|g[j]],f[i]+f[g[j]]);

    }

    if(f[(<<n)-]==inf)printf("Impossible\n");

    else printf("%d\n",f[(<<n)-]);

    return ;

}