当前位置：首页 > news >正文

打卡信奥刷题（3071）用C++实现信奥题 P6951 [ICPC 2018 WF] Wireless is the New Fiber

news 2026/6/6 12:42:35

P6951 [ICPC 2018 WF] Wireless is the New Fiber

题目描述

一种新型的无限带宽无线通信刚刚通过测试，并被证明可以替代现有的基于光纤的通信网络，后者正努力跟上流量增长的步伐。你被委托决定新通信网络的布局。当前的通信网络由一组节点（用于路由消息）和光纤链路组成，每条链路连接两个不同的节点。对于每对节点，至少存在一条（但可能更多，为了带宽目的）光纤路径。

新的通信网络将不再使用光纤。相反，它将使用无线链路，每条链路连接两个节点。这些链路具有无限带宽，但成本昂贵，因此决定尽可能少地建设这些链路以提供连通性；对于每对节点，应该只有一条路径通过无线链路连接。此外，你发现每个节点的设计都考虑了特定数量的连接。如果每个节点的连接数与今天不同，则需要重新组织，这将非常昂贵。

你的任务是设计新的网络，使其在每对节点之间恰好有一条路径，同时最小化与原始网络连接数不同的节点数量。图 K.1 显示了原始网络和样例输入 1 的解决方案。

图 K.1：样例输入 1 的示意图。

输入格式

输入以一行两个整数n ( 2 ≤ n ≤ 10 4 ) n (2 \le n \le 10^{4})n(2≤n≤104)和m ( 1 ≤ m ≤ 10 5 ) m (1 \le m \le 10^{5})m(1≤m≤105)开始，表示现有网络中的节点数和光纤链路数。节点编号从0 00到n − 1 n - 1n−1。接下来的m mm行中的每一行包含两个不同的整数a i a_{i}ai和b i b_{i}bi，表示第i ii条光纤链路连接编号为a i a_{i}ai和b i b_{i}bi的节点。保证对于每对节点，至少存在一条路径连接这两个节点。任何一对节点之间可能有多条光纤链路连接。

输出格式

显示需要更改连接数的最小节点数。从下一行开始，以与输入相同的格式显示连接系统。即，显示一行包含节点数（这将与输入相同）和无线链路数，然后在后续行中描述这些链路。如果有多种布局可能，任何有效的布局都将被接受。

输入输出样例 #1

输入 #1

7 11 0 1 0 2 0 5 0 6 1 3 2 4 1 2 1 2 1 5 2 6 5 6

输出 #1

3 7 6 0 1 0 2 0 5 0 6 3 6 4 6

输入输出样例 #2

输入 #2

4 3 0 1 2 1 2 3

输出 #2

0 4 3 2 1 1 3 0 2

说明/提示

时间限制：2 秒，内存限制：1024 MB。

SPJ 提供者：@shenyouran。

题面翻译由 ChatGPT-4o 提供。

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,m,d[10005],pl[10005];intmain(){cin>>n>>m;for(inti=1,x,y;i<=m;i++)cin>>x>>y,d[x]++,d[y]++;for(inti=0;i<n;i++)pl[i]=i,d[i]--;sort(pl,pl+n,[](intx,inty){returnd[x]<d[y];});ints=0,ans=0;for(inti=0;i<n;i++){if(s+d[pl[i]]>n-2)break;s+=d[pl[i]],ans++;}cout<<n-ans<<'\n'<<n<<' '<<n-1<<'\n';for(inti=ans;i<n;i++){if(s==n-2)d[pl[i]]=0;elsed[pl[i]]=1,s++;}sort(pl,pl+n,[](intx,inty){returnd[x]<d[y];});for(inti=0,j=0;i+2<n;i++){while(!d[pl[j]])j++;d[pl[j]]--,cout<<pl[i]<<' '<<pl[j]<<'\n';}cout<<pl[n-2]<<' '<<pl[n-1]<<'\n';}