题解：P10949 四叶草魔杖

· · 题解

P10949 四叶草魔杖

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

解法说明：

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

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

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

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

状态转移就应该是：

dp[S] \gets \min(dp[S],dp[T]+d[R])

其中 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."