[TYVJ] 2054 四叶草魔杖[Nescafé29]

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

陶醉在彩虹光芒笼罩的美景之中，探险队员们不知不觉已经穿过了七色虹，到达了目的地，面前出现了一座城堡和小溪田园，城堡前的木牌上写着“Poetic Island”。

“这一定就是另外两位护法的所在地了……我们快进去吧！”

探险队员们快步进入了城堡，城堡大厅的羊毛沙发上坐着两个人。

“你们是Nescafe的护法吧？”

“是的哦~ 我们就是圣剑护法rainbow和魔杖护法freda~ 你们来这里做什么呢~”

“我们是来拜访圣主和四位护法的……”

“可是圣主applepi已经前往超自然之界的学校（Preternatural Kingdom University，简称PKU）修炼魔法了，要想见到他，必须开启Nescafe之塔与超自然之界的通道。但是圣主规定，开启通道的方法不能告诉任何外人。我只能提示你们，开启通道的钥匙就与四位护法有关T_T”

探险队员环视四周，突然，其中一人的目光停留在了魔杖之上。“hoho~ 魔杖！传说中开启异时空通道的钥匙不就叫四叶草魔杖吗？四叶草有力量、信心、希望和幸运四片叶子，护法恰好有神刀、飞箭、圣剑、魔杖四位！aha~我找到答案了！”

“好吧，那我们就满足你们的愿望~”

描述

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

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

输入格式

第一行两个整数$$N$$、$$M$$。

第二行$$N$$个整数$$A_i$$。

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

输出格式

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

测试样例

输入

3 3
50 -20 -30
0 1 10
1 2 20
0 2 100

输出

30

备注

对于 50% 的数据，$$2 \leq N \leq 8$$。

对于 100% 的数据，$$2 \leq N \leq 16$$，$$0 \leq M \leq \frac{N \times (N-1)}{2}$$，$$0\leq p_i,q_i<N$$，$$-1000 \leq A_i \leq 1000$$，$$ 0 \leq T_i \leq 1000$$，$$ \sum A_i=0$$。

思路

最小生成树

最小生成树累加边权并判断Impossible

代码

#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[1005],fa[10005],num[1005];
struct node
{
    int u,v,val;
}e[10005];

int find_fa(int x)
{
    return (fa[x]==x)?x:fa[x]=find_fa(fa[x]);
}

bool cmp(node a,node b)
{
    return a.val<b.val;
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>e[i].u>>e[i].v>>e[i].val,num[e[i].u+1]++,num[e[i].v+1]++;
    for(int i=1;i<=n;i++)
        if(num[i]==0 && a[i])
        {
            cout<<"Impossible"<<endl;
            return 0;
        }
    int ans=0,cnt=0;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int a=find_fa(e[i].u);
        int b=find_fa(e[i].v);
        if(a!=b)
        {
            fa[a]=b;
            ans+=e[i].val;
            cnt++;
        }
        if(cnt==n-1) break;
    }
    cout<<ans;
}