题目描述

给一堆宝石 各个宝石可以 传递能量 但是开通通道是需要代价 求让所有的宝石能量都为0的最小代价。

算法1

n<=16 显然的是可以状压 考虑代价 有点像联通块 对吧 f[s]表示 形成 这个联通的最小代价 g[s]表示形成这个联通块所剩的能量 显然有 状态转移f[s|i]=min(f[s|i],f[s]+w[i]);
g[s|i]+=a[i]; 考虑 最后的答案形成 w[s]表示 形成这个状态的最小代价 且此时能量都为0;
此时我们 枚举子集 进行状态转移即可。

C++ 代码

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<iomanip>
#include<string>
#include<vector>
#include<cmath>
#include<cctype>
#define INF 1000000000
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=17,maxn=MAXN*MAXN;
int n,m,len;
int a[MAXN];
int f[1<<MAXN],g[1<<MAXN],w[1<<MAXN];//w表示组成这个状态的且能量值为0的最小代价
int b[MAXN][MAXN];
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0]=0;w[0]=0;
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
        f[1<<(i-1)]=0;g[1<<(i-1)]=a[i];
    }
    memset(b,0x3f3f3f3f,sizeof(b));
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        x=read()+1;y=read()+1;z=read();
        b[x][y]=b[y][x]=min(b[x][y],z);
    }
    for(int i=1;i<=(1<<n)-1;++i)
    {
        if(!f[i])continue;
        for(int j=1;j<=n;++j)//枚举 当前集合中存在元素
        {
            if(!(i&(1<<(j-1))))continue;
            for(int k=1;k<=n;++k)//枚举不存在元素
            {
                if(j==k)continue;
                if(!(i&(1<<(k-1))))continue;
                f[i]=min(f[i],f[i^(1<<(k-1))]+b[j][k]);
                g[i]=g[i^(1<<(k-1))]+a[k];
            }
        }
    }
    for(int i=1;i<=(1<<n)-1;++i)
    {
        w[i]=INF;
        if(g[i])continue;
        for(int j=i;j;j=(j-1)&i)
        {
            if(g[j])continue;
            w[i]=min(w[i],w[i^j]+f[j]);
        }
    }
    if(w[(1<<n)-1]==INF)printf("Impossible\n");
    else printf("%d",w[(1<<n)-1]);
    return 0;
}