本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - 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_iUiand 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_iUiVi). 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_iUiVi。但是同一对服务器之间可能有多个电缆连接。高桥希望选择一些电缆来构建一个网络以便所有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 KKU 1 U_1U1V 1 V_1V1W 1 W_1W1U 2 U_2U2V 2 V_2V2W 2 W_2W2⋮ \vdots⋮U M U_MUMV M V_MVMW M W_MWME 1 E_1E1E 2 E_2E2… \dots…E K E_KEKThe 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)(M1)-th line, the information of each cable is given overM MMlines.The( 1 i ) (1 i)(1i)-th line indicates that thei ii-th cable connects serverU i U_iUiand serverV i V_iViwith an installation cost ofW i W_iWi.IfK ≥ 1 K \geq 1K≥1, the( M 2 ) (M 2)(M2)-th line contains the cable numbersE 1 , E 2 , … , E K E_1, E_2, \dots, E_KE1,E2,…,EKthat must be included in the network, separated by spaces. IfK 0 K 0K0, 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【算法标签】#生成树【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005,M200005;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.flagy.flag;returnx.wy.w;// 其次按权重排序}intfind(intx)// 并查集的查找函数{if(p[x]!x)// 路径压缩p[x]find(p[x]);returnp[x];}intkruskal()// 最小生成树算法{sort(edges1,edgesm1);// 排序边for(inti1;in;i)// 初始化并查集p[i]i;intres0,cnt0;// res: 总权重cnt: 已选择的边数for(inti1;im;i)// 遍历所有边{intaedges[i].a,bedges[i].b,wedges[i].w;boolisRequirededges[i].flag;afind(a),bfind(b);if(a!b)// 如果两个节点不在同一集合{p[a]b;// 合并集合resw;// 累加权重cnt;// 边数加1}elseif(isRequired)// 如果边必须包含但形成环return-1;// 返回-1表示无解}if(cntn-1)// 如果边数不足n-1return-1;// 返回-1表示无解returnres;// 返回最小生成树的总权重}signedmain(){cinnmk;// 输入节点数、边数和必须包含的边数for(inti1;im;i)// 输入边的信息{cinedges[i].aedges[i].bedges[i].w;edges[i].flagfalse;// 初始化为非必须}for(inti1;ik;i)// 标记必须包含的边{inte;cine;edges[e].flagtrue;}coutkruskal()endl;// 输出最小生成树的总权重return0;}【运行结果】4 5 1 1 2 3 2 3 1 1 3 2 3 4 4 2 4 5 1 8
题解：AtCoder AT_awc0080_d Network Construction
发布时间：2026/6/1 16:21:21
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - 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_iUiand 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_iUiVi). 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_iUiVi。但是同一对服务器之间可能有多个电缆连接。高桥希望选择一些电缆来构建一个网络以便所有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 KKU 1 U_1U1V 1 V_1V1W 1 W_1W1U 2 U_2U2V 2 V_2V2W 2 W_2W2⋮ \vdots⋮U M U_MUMV M V_MVMW M W_MWME 1 E_1E1E 2 E_2E2… \dots…E K E_KEKThe 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)(M1)-th line, the information of each cable is given overM MMlines.The( 1 i ) (1 i)(1i)-th line indicates that thei ii-th cable connects serverU i U_iUiand serverV i V_iViwith an installation cost ofW i W_iWi.IfK ≥ 1 K \geq 1K≥1, the( M 2 ) (M 2)(M2)-th line contains the cable numbersE 1 , E 2 , … , E K E_1, E_2, \dots, E_KE1,E2,…,EKthat must be included in the network, separated by spaces. IfK 0 K 0K0, 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【算法标签】#生成树【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005,M200005;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.flagy.flag;returnx.wy.w;// 其次按权重排序}intfind(intx)// 并查集的查找函数{if(p[x]!x)// 路径压缩p[x]find(p[x]);returnp[x];}intkruskal()// 最小生成树算法{sort(edges1,edgesm1);// 排序边for(inti1;in;i)// 初始化并查集p[i]i;intres0,cnt0;// res: 总权重cnt: 已选择的边数for(inti1;im;i)// 遍历所有边{intaedges[i].a,bedges[i].b,wedges[i].w;boolisRequirededges[i].flag;afind(a),bfind(b);if(a!b)// 如果两个节点不在同一集合{p[a]b;// 合并集合resw;// 累加权重cnt;// 边数加1}elseif(isRequired)// 如果边必须包含但形成环return-1;// 返回-1表示无解}if(cntn-1)// 如果边数不足n-1return-1;// 返回-1表示无解returnres;// 返回最小生成树的总权重}signedmain(){cinnmk;// 输入节点数、边数和必须包含的边数for(inti1;im;i)// 输入边的信息{cinedges[i].aedges[i].bedges[i].w;edges[i].flagfalse;// 初始化为非必须}for(inti1;ik;i)// 标记必须包含的边{inte;cine;edges[e].flagtrue;}coutkruskal()endl;// 输出最小生成树的总权重return0;}【运行结果】4 5 1 1 2 3 2 3 1 1 3 2 3 4 4 2 4 5 1 8
