题解：AtCoder AT_awc0080_d Network Construction

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：D - Network Construction

【题目描述】

Takahashi is the network administrator of a data center withN NNservers. The servers are numbered from1 11toN NN.

There areM MMavailable cables for connecting servers, and the cables are also numbered from1 11toM MM. Thei ii-th cable( 1 ≤ i ≤ M ) (1 \leq i \leq M)(1≤i≤M)bidirectionally connects serverU i U_iUi​and serverV i V_iVi​, with an installation cost ofW i W_iWi​. Each cable connects two distinct servers (i.e.,U i ≠ V i U_i \neq V_iUi​=Vi​). However, there may be multiple cables connecting the same pair of servers.

Takahashi wants to select some cables to build a network so that allN NNservers can communicate with each other. The set of selected cables must form aspanning tree. A spanning tree is a graph that includes allN NNservers as vertices, where all servers are connected by the selected cables, and no cycles exist (in this case, exactlyN − 1 N-1N−1cables are selected).

However, due to security requirements, a specific set ofK KKcables (numberedE 1 , E 2 , … , E K E_1, E_2, \dots, E_KE1​,E2​,…,EK​) have already been contracted as dedicated encrypted communication lines and must be included in the network.

If a spanning tree exists that contains allK KKspecified cables, output the minimum total installation cost of theN − 1 N-1N−1cables included in that spanning tree. If no such spanning tree exists, output− 1 -1−1.

高桥是一个数据中心的网络管理员，该中心有N NN台服务器。服务器编号为1 11到N NN。

有M MM条可用的电缆用于连接服务器，电缆也编号为1 11到M MM。第i ii条电缆（1 ≤ i ≤ M 1 \leq i \leq M1≤i≤M）双向连接服务器U i U_iUi​和服务器V i V_iVi​，安装成本为W i W_iWi​。每条电缆连接两台不同的服务器（即U i ≠ V i U_i \neq V_iUi​=Vi​）。但是，同一对服务器之间可能有多个电缆连接。

高桥希望选择一些电缆来构建一个网络，以便所有N NN台服务器可以相互通信。选中的电缆集合必须构成一棵生成树。生成树是一个图，以所有N NN台服务器为顶点，其中所有服务器通过选中的电缆连接，且不存在环（在这种情况下，恰好选中N − 1 N-1N−1条电缆）。

然而，由于安全要求，一组特定的K KK条电缆（编号为E 1 , E 2 , … , E K E_1, E_2, \dots, E_KE1​,E2​,…,EK​）已经签约作为专用加密通信线路，必须包含在网络中。

如果存在一棵包含所有K KK条指定电缆的生成树，则输出该生成树中包含的N − 1 N-1N−1条电缆的最小总安装成本。如果不存在这样的生成树，输出− 1 -1−1。

【输入】

N NNM MMK KK
U 1 U_1U1​V 1 V_1V1​W 1 W_1W1​
U 2 U_2U2​V 2 V_2V2​W 2 W_2W2​
⋮ \vdots⋮
U M U_MUM​V M V_MVM​W M W_MWM​
E 1 E_1E1​E 2 E_2E2​… \dots…E K E_KEK​

• The first line contains the number of serversN NN, the number of available cablesM MM, and the number of cables that must be includedK KK, separated by spaces.
• From the 2nd line to the( M + 1 ) (M + 1)(M+1)-th line, the information of each cable is given overM MMlines.
• The( 1 + i ) (1 + i)(1+i)-th line indicates that thei ii-th cable connects serverU i U_iUi​and serverV i V_iVi​with an installation cost ofW i W_iWi​.
• IfK ≥ 1 K \geq 1K≥1, the( M + 2 ) (M + 2)(M+2)-th line contains the cable numbersE 1 , E 2 , … , E K E_1, E_2, \dots, E_KE1​,E2​,…,EK​that must be included in the network, separated by spaces. IfK = 0 K = 0K=0, this line does not exist.

【输出】

If a spanning tree exists that contains allK KKspecified cables, output in one line the minimum total installation cost of theN − 1 N-1N−1cables included in that spanning tree. If no such spanning tree exists, output− 1 -1−1.

【输入样例】

4 5 1 1 2 3 2 3 1 1 3 2 3 4 4 2 4 5 1

【输出样例】

8

【算法标签】

#生成树

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005,M=200005;intn,m,k;// n: 节点数，m: 边数，k: 必须包含的边数intp[N];// 并查集数组structEdge{inta,b,w;// 边的两个端点和权重boolflag;// 标记是否为必须包含的边}edges[M];booloperator<(Edge x,Edge y)// 重载小于运算符，用于排序{if(x.flag!=y.flag)// 优先排序必须包含的边returnx.flag>y.flag;returnx.w<y.w;// 其次按权重排序}intfind(intx)// 并查集的查找函数{if(p[x]!=x)// 路径压缩p[x]=find(p[x]);returnp[x];}intkruskal()// 最小生成树算法{sort(edges+1,edges+m+1);// 排序边for(inti=1;i<=n;i++)// 初始化并查集p[i]=i;intres=0,cnt=0;// res: 总权重，cnt: 已选择的边数for(inti=1;i<=m;i++)// 遍历所有边{inta=edges[i].a,b=edges[i].b,w=edges[i].w;boolisRequired=edges[i].flag;a=find(a),b=find(b);if(a!=b)// 如果两个节点不在同一集合{p[a]=b;// 合并集合res+=w;// 累加权重cnt++;// 边数加1}elseif(isRequired)// 如果边必须包含但形成环return-1;// 返回-1表示无解}if(cnt<n-1)// 如果边数不足n-1return-1;// 返回-1表示无解returnres;// 返回最小生成树的总权重}signedmain(){cin>>n>>m>>k;// 输入节点数、边数和必须包含的边数for(inti=1;i<=m;i++)// 输入边的信息{cin>>edges[i].a>>edges[i].b>>edges[i].w;edges[i].flag=false;// 初始化为非必须}for(inti=1;i<=k;i++)// 标记必须包含的边{inte;cin>>e;edges[e].flag=true;}cout<<kruskal()<<endl;// 输出最小生成树的总权重return0;}

【运行结果】

4 5 1 1 2 3 2 3 1 1 3 2 3 4 4 2 4 5 1 8