C++ 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 17,M = N * N;
int mod = 1e9 +7;
int n,m,k,S,T;
int w[1 << N];
int a[N],f[1 << N];
struct node{
    int a,b,c;
    bool operator<(const node &t)const{
        return c < t.c;
    }
}e[M];
int sum[1 << N];
int p[N];
int find(int x){
    if(p[x] != x) return p[x] = find(p[x]);
    return x;
}
int kruscal(int x){
    int tot = 0;
    //求出集合中包含哪些点 
    for(int i = 0 ; i < n ; ++i){
        if(x >> i & 1){
            tot++;
            p[i] = i;
        }
    }
    int res = 0,cnt = 0;
    for(int i = 0 ; i < m ; ++i){
        int a = e[i].a,b = e[i].b,c = e[i].c;
        //若a或b不在该集合中跳过 
        if(!(x >> a & 1) || !(x >> b & 1)) continue;
        a = find(a),b = find(b);
        if(a != b){
            p[a] = b;
            cnt++;
            res += c;
        }
    }
    //若没有最小生成树
    if(cnt  + 1 != tot) res = INF;
    return res;
} 
void solve(){
    cin >> n >> m;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    for(int i = 0 ; i < m ; ++i){
        int a,b,c;
        cin >> a >> b >> c;
        e[i] = {a,b,c};
    }
    sort(e,e + m);
    for(int i = 0 ; i < 1 << n ; ++i){
        for(int j = 0 ; j < n ; ++j){
            //二进制枚举将每位为1位置的物品放入i集合中
            if(i >> j & 1) sum[i] += a[j]; 
        }
    }
    for(int i = 0 ; i < 1 << n ; ++i){
        //计算所有权值和为0的集合的最小生成树 
        if(sum[i] == 0) w[i] = kruscal(i);
    }
    memset(f,0x3f,sizeof(f));
    f[0] = 0;
    //把每个集合当成背包中的物品
    //将所有权值为0的集合组成原所有点
    for(int i = 0 ; i < 1 << n ; ++i) if(!sum[i]){
        for(int j = 0 ; j < 1 << n ; ++j) if(!sum[j]){
            if(i & j) continue;
            f[i | j] = min(f[i | j],f[i] + w[j]);
        }
    }
    if(f[(1 << n) - 1] == INF) cout << "Impossible" << endl;
    else cout << f[(1 << n) - 1] << endl;
}

signed main(){
    IOS;
    solve();
    return 0;
}