A171747.Yuilice -题解

简单上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20,M=1<<N;
int n,m,conf[N];
ll t[N],dp[M];
struct B{int m;ll c;};
vector<B>vb;
vector<int>bc[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if(!(cin>>n>>m))return 0;
    for(int i=0;i<n;++i)cin>>t[i];
    for(int i=0;i<m;++i){
        int u,v;cin>>u>>v;u--;v--;
        conf[u]|=1<<v;conf[v]|=1<<u;
    }
    for(int i=0;i<n;++i)vb.push_back({1<<i,t[i]});
    for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)if(!(conf[i]&(1<<j)))vb.push_back({(1<<i)|(1<<j),max(t[i],t[j])});
    for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)if(!(conf[i]&(1<<j)))for(int k=j+1;k<n;++k)if(!(conf[i]&(1<<k))&&!(conf[j]&(1<<k)))vb.push_back({(1<<i)|(1<<j)|(1<<k),max({t[i],t[j],t[k]})});
    for(int i=0;i<(int)vb.size();++i)for(int k=0;k<n;++k)if(vb[i].m&(1<<k))bc[k].push_back(i);
    int S=1<<n;
    fill(dp,dp+S,LLONG_MAX);
    dp[0]=0;
    for(int mask=0;mask<S;++mask){
        if(dp[mask]==LLONG_MAX)continue;
        int rem=(~mask)&(S-1);
        if(!rem)continue;
        int f=__builtin_ctz(rem);
        for(int idx:bc[f]){
            B&b=vb[idx];
            if(b.m&mask)continue;
            int nm=mask|b.m;
            dp[nm]=min(dp[nm],dp[mask]+b.c);
        }
    }
    cout<<dp[S-1]<<endl;
    return 0;
}