P10949 四叶草魔杖

来源：算法进阶图论（练习）：四叶草魔杖

解法说明：

提示：此题样例应输出 $30$。

根据题目的数据范围，不难想到可以用状态压缩来解。

可是两个宝石能量的传递应该如何解决？我们把题目简化为在宝石 $i$ 和宝石 $j$ 之间传递能量的代价为 $w$，结果发现这和最小生成树的模版题很像。

我们定义一个数组，$dp[S]$ 表示当前宝石集合为 $S$ 传递完毕时花费的最小代价。其中 $S$ 是一个二进制数，它的第 $i$ 位为 $1$ 代表着 $S$ 集合中有宝石 $i$。

状态转移就应该是：

其中 $T$ 和 $R$ 是 $S$ 的子集，$T \cup R$ 为 $S$。$d[R]$ 表示 $R$ 集合中宝石传递完毕的最小代价，可以用最小生成树计算出 $d[R]$ 的值。

可是我们发现：把每个宝石集合都计算一遍最小生成树，最后计算出来的总最小代价却有可能不是最优的。且最初的图不一定连通，一个个求最小生成树会无端多出很多时间。

我们考虑只计算宝石能量值总和为 $0$ 的集合，这样最后计算出的代价一定最优，且算法也更简洁。

还有点小细节，写在代码注释了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10, inf=0x3f3f3f3f;
struct node{int x, y, c;} e[N];
int s[N], id[N], a[N], d[N], n, fa[N], m, dp[N]; //数组含义见上面文字
bool cmp(node n1, node n2) {return n1.c<n2.c;}
int findfa(int x) {return (fa[x]==x)? fa[x]: fa[x]=findfa(fa[x]);}
int Kruskal(int S){
    memset(fa, 0, sizeof(fa)); int ans=0;
    for(int i=1; i<=n; i++) 
        if((1<<(i-1))&S) fa[i]=i; //只有宝石i在当前集合S中时才执行

    for(int i=1; i<=m; i++){
        int x=e[i].x, y=e[i].y, c=e[i].c;
        if((!((1<<(x-1))&S)) || (!((1<<(y-1))&S))) //不在当前集合对答案无意义
            continue;
        int tx=findfa(x), ty=findfa(y);
        if(tx!=ty){
            ans+=c;
            fa[tx]=ty;
        }
    }

    int flag=-1;
    for(int i=1; i<=n; i++) if((1<<(i-1))&S){
        if(flag==-1) flag=findfa(i);
        else if(flag!=findfa(i)) return inf; //当前集合不连通，无解
    }
    return ans;

}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].c);
        e[i].x++; e[i].y++;
    }

    if(m==0) {printf("0\n"); return 0;} //防止hack数据
    
    memset(s, 0, sizeof(s));
    for(int i=0; i<(1<<n); i++)
        for(int j=1; j<=n; j++) if((1<<(j-1))&i)
            s[i]+=a[j]; //s[i]存的是i集合中所有宝石的能量总和

    int len=0; memset(d, 0x3f, sizeof(d));
    sort(e+1, e+m+1, cmp); //排序之后就能保证是最小生成树
    for(int i=1; i<(1<<n); i++) if(s[i]==0){
        id[++len]=i; //当前集合i宝石的能量总和为0，记录一下
        d[i]=Kruskal(i);
    }

    memset(dp, 0x3f, sizeof(dp)); dp[0]=0;
    for(int x=1; x<=len; x++){
        int i=id[x];
        for(int j=i; j; j=(j-1)&i) //这里的j枚举的是i所有少一个1的状态 
        //因为之前记录是从小到大，所以i的子集如果合法的话一定在i之前更新了，可以放心用
            dp[i]=min(dp[i], dp[i^j]+d[j]); //状态转移
        //虽然最后dp[j]<=d[j]，但这里dp[j]有可能还没被更新，所以先用d[j]
    }
    if(dp[(1<<n)-1]==inf) printf("Impossible\n");
    else printf("%d\n", dp[(1<<n)-1]); //所有宝石传递完毕的最小代价
    return 0;
}

感谢观看。

"‌In bocca al lupo."

洛谷P10949 四叶草魔杖 [最小生成树]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10, inf=0x3f3f3f3f;
struct node{int x, y, c;} e[N];
int s[N], id[N], a[N], d[N], n, fa[N], m, dp[N]; //数组含义见上面文字
bool cmp(node n1, node n2) {return n1.c<n2.c;}
int findfa(int x) {return (fa[x]==x)? fa[x]: fa[x]=findfa(fa[x]);}
int Kruskal(int S){
    memset(fa, 0, sizeof(fa)); int ans=0;
    for(int i=1; i<=n; i++) 
        if((1<<(i-1))&S) fa[i]=i; //只有宝石i在当前集合S中时才执行

    for(int i=1; i<=m; i++){
        int x=e[i].x, y=e[i].y, c=e[i].c;
        if((!((1<<(x-1))&S)) || (!((1<<(y-1))&S))) //不在当前集合对答案无意义
            continue;
        int tx=findfa(x), ty=findfa(y);
        if(tx!=ty){
            ans+=c;
            fa[tx]=ty;
        }
    }

    int flag=-1;
    for(int i=1; i<=n; i++) if((1<<(i-1))&S){
        if(flag==-1) flag=findfa(i);
        else if(flag!=findfa(i)) return inf; //当前集合不连通，无解
    }
    return ans;

}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].c);
        e[i].x++; e[i].y++;
    }

    if(m==0) {printf("0\n"); return 0;} //防止hack数据
    
    memset(s, 0, sizeof(s));
    for(int i=0; i<(1<<n); i++)
        for(int j=1; j<=n; j++) if((1<<(j-1))&i)
            s[i]+=a[j]; //s[i]存的是i集合中所有宝石的能量总和

    int len=0; memset(d, 0x3f, sizeof(d));
    sort(e+1, e+m+1, cmp); //排序之后就能保证是最小生成树
    for(int i=1; i<(1<<n); i++) if(s[i]==0){
        id[++len]=i; //当前集合i宝石的能量总和为0，记录一下
        d[i]=Kruskal(i);
    }

    memset(dp, 0x3f, sizeof(dp)); dp[0]=0;
    for(int x=1; x<=len; x++){
        int i=id[x];
        for(int j=i; j; j=(j-1)&i) //这里的j枚举的是i所有少一个1的状态 
        //因为之前记录是从小到大，所以i的子集如果合法的话一定在i之前更新了，可以放心用
            dp[i]=min(dp[i], dp[i^j]+d[j]); //状态转移
        //虽然最后dp[j]<=d[j]，但这里dp[j]有可能还没被更新，所以先用d[j]
    }
    if(dp[(1<<n)-1]==inf) printf("Impossible\n");
    else printf("%d\n", dp[(1<<n)-1]); //所有宝石传递完毕的最小代价
    return 0;
}

【题解】[洛谷P10949] 四叶草魔杖 [最小生成树]-CSDN博客

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10, inf=0x3f3f3f3f;
struct node{int x, y, c;} e[N];
int s[N], id[N], a[N], d[N], n, fa[N], m, dp[N]; //数组含义见上面文字
bool cmp(node n1, node n2) {return n1.c<n2.c;}
int findfa(int x) {return (fa[x]==x)? fa[x]: fa[x]=findfa(fa[x]);}
int Kruskal(int S){
    memset(fa, 0, sizeof(fa)); int ans=0;
    for(int i=1; i<=n; i++) 
        if((1<<(i-1))&S) fa[i]=i; //只有宝石i在当前集合S中时才执行
for(int i=1; i&lt;=m; i++){
    int x=e[i].x, y=e[i].y, c=e[i].c;
    if((!((1&lt;&lt;(x-1))&amp;S)) || (!((1&lt;&lt;(y-1))&amp;S))) //不在当前集合对答案无意义
        continue;
    int tx=findfa(x), ty=findfa(y);
    if(tx!=ty){
        ans+=c;
        fa[tx]=ty;
    }
}

int flag=-1;
for(int i=1; i&lt;=n; i++) if((1&lt;&lt;(i-1))&amp;S){
    if(flag==-1) flag=findfa(i);
    else if(flag!=findfa(i)) return inf; //当前集合不连通，无解
}
return ans;

}
int main(){
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=m; i++){
scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].c);
e[i].x++; e[i].y++;
}
if(m==0) {printf("0\n"); return 0;} //防止hack数据

memset(s, 0, sizeof(s));
for(int i=0; i&lt;(1&lt;&lt;n); i++)
    for(int j=1; j&lt;=n; j++) if((1&lt;&lt;(j-1))&amp;i)
        s[i]+=a[j]; //s[i]存的是i集合中所有宝石的能量总和

int len=0; memset(d, 0x3f, sizeof(d));
sort(e+1, e+m+1, cmp); //排序之后就能保证是最小生成树
for(int i=1; i&lt;(1&lt;&lt;n); i++) if(s[i]==0){
    id[++len]=i; //当前集合i宝石的能量总和为0，记录一下
    d[i]=Kruskal(i);
}

memset(dp, 0x3f, sizeof(dp)); dp[0]=0;
for(int x=1; x&lt;=len; x++){
    int i=id[x];
    for(int j=i; j; j=(j-1)&amp;i) //这里的j枚举的是i所有少一个1的状态 
    //因为之前记录是从小到大，所以i的子集如果合法的话一定在i之前更新了，可以放心用
        dp[i]=min(dp[i], dp[i^j]+d[j]); //状态转移
    //虽然最后dp[j]&lt;=d[j]，但这里dp[j]有可能还没被更新，所以先用d[j]
}
if(dp[(1&lt;&lt;n)-1]==inf) printf("Impossible\n");
else printf("%d\n", dp[(1&lt;&lt;n)-1]); //所有宝石传递完毕的最小代价
return 0;

}