ACWing 388 四叶草魔杖 题解

ACWing 388 四叶草魔杖 题解

xiaoh 2020-5-2

题意

给定有$n$个数的序列$a$($1\leq n\leq 16$),保证$\sum a=0$.有$m$个三元组$(p_i,q_i,T_i)$,我们可以花费$T_i$的代价使$p_i$与$q_i$中的一个$-t$,一个$+t$($t$可以为任意的正整数)，求使序列$a$的所有数变为$0$的最小代价.

题解

考虑如何能够使所有的数变为$0$.我们发现,选取一些$a_{b_1},a_{b_2},\dots,a_{b_c}$,使其和为$0$.则我们将这些$b_1,b_2,\dots,b_c$,视为点,转换关系的三元组视为边,则其最小生成树即为使这些数都变为$0$的最小代价.又因为数据非常小,所以我们可以$2^n$遍历所有可能的点并计算哪些$a$的子序列的和为$0$,并计算使其全部变为$0$的生成树的代价.

那么如何使所有的数都变为$0$呢?我们可以将其理解为将多个包含的点集不重复、不遗漏的生成树构成一个森林,其中每棵树的点权和为$0$.那么鉴于我们之前已经求出所有可行的生成树,我们直接采用状压$DP$进行统计即可.时间复杂度$O(2^nn)$.

Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=20,MAXM=125;
const int inf=999999;
int n,m;
int a[MAXN];
int mp[MAXN][MAXN];
bool book[MAXN];
int cnt=0;
struct node{
    int pos,val;
}b[100010];
int tot=0;
int tmp[MAXN];
int dis[MAXN];
bool inq[MAXN];
inline int prim()
{
    tot=0;
    memset(inq,0,sizeof(inq));
    for(int i=1;i<=n;i++) dis[i]=inf;
    for(int i=1;i<=n;i++)
    if(book[i]) tmp[++tot]=i;
    if(tot<=1) return 0;
    dis[tmp[1]]=0;
    int ans=0;
    for(int i=1;i<=tot;i++)
    {
        int pos=0,val=inf;
        for(int j=1;j<=tot;j++)
        if(!inq[tmp[j]]&&dis[tmp[j]]<val) pos=j,val=dis[tmp[j]];
        if(val==inf) return inf;
        inq[tmp[pos]]=1,ans+=dis[tmp[pos]];
        for(int j=1;j<=tot;j++)
        if(!inq[tmp[j]]) dis[tmp[j]]=min(dis[tmp[j]],mp[tmp[pos]][tmp[j]]);
    }
    ans=min(ans,inf);
    return ans;
}
void dfs(int step,int tot,int val)
{
    if(step==n+1)
    {
        if(tot==0&&val) b[++cnt]={val,prim()};
        return;
    }
    book[step]=0;
    dfs(step+1,tot,val);
    book[step]=1;
    dfs(step+1,tot+a[step],val|(1<<(step-1)));
    book[step]=0;
}
int f[100010];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) mp[i][j]=(i==j)? 0:inf;
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        u++,v++;
        mp[u][v]=mp[v][u]=c;
    }
    dfs(1,0,0);
    for(int i=1;i<=(1<<n)-1;i++) f[i]=inf;
    for(int i=1;i<=cnt;i++)
    for(int j=(1<<n)-1;j>=1;j--)
    if((j&b[i].pos)==b[i].pos) f[j]=min(f[j],f[j^b[i].pos]+b[i].val);
    if(f[(1<<n)-1]<inf) cout<<f[(1<<n)-1]<<endl;
    else cout<<"Impossible"<<endl;
	return 0;
}