tyvj 2054 [Nescafé29]四叶草魔杖——最小生成树+状压dp

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

枚举点集，如果其和为0，则作为一个独立的块求一下最小生成树。因为它可以不和别的块连边。

然后状压dp即可。

别忘了判断该块能不能连通。

别忘了判断无解！（0x3f 真好用）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,M=N*(N-)/,Lm=(<<)+;

int n,m,a[N],hd[N],c[Lm],lm,v[Lm],cnt,dp[Lm],fa[N];

bool vis[Lm];

struct Ed{

    int x,y,w;

    Ed(int x=,int y=,int w=):x(x),y(y),w(w) {}

}ed[M];

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

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

void kruscal(int s,int &k)

{

    for(int i=;i<=n;i++)fa[i]=i;

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

    {

        int x=ed[i].x,y=ed[i].y;

        if(((<<(x-))&s)&&((<<(y-))&s)&&find(x)!=find(y))

        {

            fa[(find(x))]=find(y);c[k]+=ed[i].w;

        }

    }

    int tf=;

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

      if((<<i)&s)

        {

          if(!tf)tf=find(i+);

          else if(find(i+)!=tf){v[k]=c[k]=;k--;return;}

        }

}

void init()

{

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

    for(int s=;s<lm;s++)

    {

        int sum=;

        for(int j=;j<n;j++) if((<<j)&s) sum+=a[j+];

        if(sum)continue;

        v[++cnt]=s;kruscal(s,cnt);

    }

}

void dfs(int s)

{

    if(vis[s])return;vis[s]=;

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

        if((s&v[i])==v[i])

        {

            dfs(s-v[i]);dp[s]=min(dp[s],dp[s-v[i]]+c[i]);

        }

}

int main()

{

    scanf("%d%d",&n,&m);int x,y,z;lm=(<<n);

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

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

    {

        scanf("%d%d%d",&x,&y,&z);

        ed[i]=Ed(x+,y+,z);

    }

    init();

    memset(dp,0x3f,sizeof dp);dp[]=;

    dfs(lm-);

    if(dp[lm-]==0x3f3f3f3f)printf("Impossible");

    else printf("%d",dp[lm-]);

    return ;

}