[kuangbin带你飞]专题六最小生成树 E - QS Network

末蓝、 2023-08-17 15:41 101阅读 0赞

# E - QS Network #

题目链接：

[https://vjudge.net/contest/66965\#problem/E][https_vjudge.net_contest_66965_problem_E]

题目：

在星系cgb的w-503行星中，有一种名为QS的智能生物。 QS通过网络相互通信。如果两个QS想要连接，他们需要购买两个网络适配器（每个QS一个）和一段网络电缆。请注意，一个网络适配器只能在单个连接中使用。（即，如果QS想要设置四个连接，则需要购买四个适配器）。在通信过程中，QS将其消息广播到它所连接的所有QS，接收消息的QS组将消息广播到它们所连接的所有QS，重复该过程直到所有QS都收到消息。  
  
    示例如下所示：  
  
  
    QS网络示例，QS A想要发送消息。  
  
    步骤1. QS A向QS B和QS C发送消息;  
  
    步骤2. QS B向QS A发送消息; QS C向QS A和QS D发送消息;  
  
    步骤3.该过程终止，因为所有QS都收到了该消息。  
  
    每个QS都有其优质的网络适配器品牌，并始终在其所有连接中购买该品牌。 QS之间的距离也不同。考虑到每个QS优先品牌的网络适配器的价格以及每对QS之间的电缆价格，您的任务是编写一个程序来确定设置QS网络的最低成本。  
  
  
输入  
  
    输入的第一行包含一个整数t，表示数据集的数量。  
  
    从第二行开始，有t个数据集。  
  
    在单个数据集中，第1行包含一个表示QS数的整数n。  
  
    第二行包含n个整数，表示每个QS最喜欢的网络适配器的价格。  
  
    在第3行到第n + 2行包含一个矩阵，表示ecah对QS之间的电缆价格。  
  
    限制：  
  
    输入中的所有整数都是非负数且不超过1000。  
  
  
产量  
  
    对于每个数据集，输出一行中的最小成本。不需要额外的空行。  
  
  
样本输入  
  
    1  
    3  
    10 20 30  
    0 100 200  
    100 0 300  
    200 300 0  
  
  
样本输出  
  
    370

**思路：这道题要处理的东西比模板多一点，就是每个QS都有自己喜欢的适配器价格，然而两人之间需要有电缆，电缆也因人而异，**

**所以以往的node\[i\].w+=x改成node\[i\].w+=x+a\[i\]+a\[j\]，就是两者之间的适配器加上i->j和j->i之间的电缆价格就行了，主意数组要开大**

**我用的2e5+10wa掉了，用的2e6+10就ac了**

//
    // Created by hy on 2019/7/30.
    //
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <set>
    using namespace std;
    typedef long long ll;
    const int maxn=2e6+10;
    int father[maxn],a[maxn];
    struct Node{
        int u,v,w;
        bool operator<(const Node &other)const{
            return this->w<other.w;
        }
    }node[maxn];
    int find(int x)
    {
        if(x==father[x])
            return x;
        return father[x]=find(father[x]);
    }
    int main()
    {
        int T;
        int n;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            for(int i=0;i<=n;i++)
                father[i]=i;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            int p;
            int m=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                  scanf("%d",&p);
                  node[m].u=i;
                  node[m].v=j;
                  node[m++].w=p+a[i]+a[j];
                }
            }
            int sum=0;
            int cnt=0;
            sort(node,node+m);
            for(int i=0;i<m;i++)
            {
                int uu=find(node[i].u);
                int vv=find(node[i].v);
                if(uu==vv)
                    continue;
                else
                {
                    sum+=node[i].w;
                    father[uu]=vv;
                    cnt++;
                    if(cnt==n-1)
                        break;
                }
            }
            printf("%d\n",sum);
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11273568.html

[https_vjudge.net_contest_66965_problem_E]: https://vjudge.net/contest/66965#problem/E