3、四叶草魔杖3809

(magic.cpp/pas)

【问题描述】

　　魔杖护法Freda融合了四件武器，于是魔杖顶端缓缓地生出了一棵四叶草，四片叶子幻发着淡淡的七色光。圣剑护法rainbow取出了一个圆盘，圆盘上镶嵌着N颗宝石，编号为0~N-1。第i颗宝石的能量是Ai。如果Ai>0，表示这颗宝石能量过高，需要把Ai的能量传给其它宝石；如果Ai<0，表示这颗宝石的能量过低，需要从其它宝石处获取-Ai的能量。保证∑Ai=0。只有当所有宝石的能量均相同时，把四叶草魔杖插入圆盘中央，才能开启超自然之界的通道。 

　　不过，只有M对宝石之间可以互相传递能量，其中第i对宝石之间无论传递多少能量，都要花费Ti的代价。探险队员们想知道，最少需要花费多少代价才能使所有宝石的能量都相同？

【输入】

　　第一行两个整数N、M。 

　　第二行N 个整数Ai。 

　　接下来M行每行三个整数pi,qi,Ti，表示在编号为pi和qi的宝石之间传递能量需要花费Ti的代价。数据保证每对pi、qi最多出现一次。

【输出】

　　输出一个整数表示答案。无解输出Impossible。

【输入样例】

3 3

50 -20 -30

0 1 10

1 2 20

0 2 100

【输出样例】

30

【数据规模】

　　 对于50%的数据，2<=N<=8。 

　　对于100%的数据，2<=N<=16，0<=M<=N*(N-1)/2，0<=pi,qi<n，-1000<=ai<=1000，

0<=Ti<=1000，∑Ai=0。

 

 

 

 

 

 

【分析】树形DP 

动态规划、最小生成树、状态压缩

      1.找出所有能量和为0的集合。

          若该集合的点是联通的，那么求出该集合的最小生成树，生成树的值即是该集合能量转移所需最小代价

      2.将每一和为0的集合看成是一个物品，利用背包动规求出最优解。

      具体做法是：

          用二进制来压缩状态，1代表节点在集合中，0代表不在。

          比如数字s的二进制形式为100111，表明0,1,2,5号节点在s表示的集合中。

      题目最多有n(n<=16)个节点，因此s的范围是0到(2^n)-1 也就是(1<<n)-1 

      用数组Sum[s]，记录集合s中包含的节点的能量之和。 

      对于每一个能量和为0的集合x(Sum[x]==0)，若能得到一棵最小生成树，用数组Cost[x]记录下该生成树的代价

      f[i]记录平衡集合i中的节点的能量值，所需最小代价 

      对于集合i和j,若满足Sum[i]==true且Sum[j]==true

      那么有f[i|j]=min(f[i|j],f[i]+Cost[j]); 

      i|j表示集合i与集合j合并之后的集合 

 

 

 

code：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define N 1000006  6 using namespace std; 7 struct node { 8     int u,v,w; 9 } e[N];10 int dp[N],f[N],a[N],fa[N];11 int cnt;12 void add(int u,int v,int w) {13     e[++cnt].u=u;14     e[cnt].v=v;15     e[cnt].w=w;16 }17 bool cmp(const node&a,const node&b) {18     return a.w
         
          >(i-1))&1)all++;27     for(int i=1; i<=m; i++) {28     //    cout<
          
           <<" "<
           
            <<'\n';29 if(((S>>(e[i].u-1))&1)&&((S>>(e[i].v-1))&1)) {30 int u=e[i].u,v=e[i].v;31 if(find(u)!=find(v)) {32 merge(u,v);33 ans+=e[i].w;34 cnt_++;35 if(cnt_==all-1)return ans;36 }37 }38 }39 return ans;40 }41 int main() {42 cin>>n>>m;43 for(int i=1; i<=n; i++)cin>>a[i];44 for(int i=1; i<=m; i++) {45 int u,v,w;46 cin>>u>>v>>w;47 u++,v++;48 add(v,u,w);49 }50 sort(e+1,e+cnt+1,cmp);51 int all=(1<
            
             >(j-1))&1) {56 sum+=a[j];57 fa[j]=j;58 }59 }60 if(sum)continue;61 f[i]=kruskal(i);62 }63 memset(dp,0x3f3f3f3f,sizeof dp);64 dp[0]=0;65 for(int i=1;i<=all;i++){66 if(f[i]==0)continue;67 for(int j=all;j>=0;j--){68 if((i&j)==i){69 dp[j]=min(dp[j],dp[j&(~i)]+f[i]);70 }71 }72 }73 if(dp[all]==0x3f3f3f3f){74 cout<<"Impossible";75 return 0;76 }77 else cout<
            
           
          
         
        
       
      
     

over