道路升级发表时间：2022-10-27 20:16 道路升级 问题描述 Z 国有 n 个城市和 m 条双向道路，每条道路连接了两个不同的城市，保证所有城市之间都可以通过这些道路互达。每条道路都有一个载重量限制，这限制了通过这条道路的货车最大的载重量。道路的编号从 1 至 m 。巧合的是，所有道路的载重量限制恰好都与其编号相同。 现在，要挑选出若干条道路，将它们升级成高速公路，并满足如下要求： 所有城市之间都可以通过高速公路互达。 对于任意两个城市 u,v 和足够聪明的货车司机：只经过高速公路从 u 到达 v 能够装载货物的最大重量，与经过任意道路从 u 到达 v 能够装载货物的最大重量相等。（足够聪明的司机只关注载重量，并不在意绕路） 在上面的前提下，要求选出的道路数目尽可能少。 求需要挑选出哪些道路升级成高速公路（如果有多种方案请任意输出一种）。 输入 第一行 2 个用空格隔开的整数 n,m ，分别表示城市数目、道路数目。 第 2 行到第 m+1 行，每行 2 个用空格隔开的整数 u,v 描述一条从 u 到 v 的双向道路，第 i+1 行的道路的编号为 i 。 注意：数据只保证不存在连接的城市相同的道路（自环），并不保证不存在两条完全相同的边（重边） 输 第一行一个整数 k ，表示升级成高速公路的道路数。 接下来 k 行每行一个整数，从小到大输出所有选出的道路的编号。 输入样例 输样例 数据范围 对于 20% 的数据，保证 n≤5，m≤10。 对于 60% 的数据，保证 n≤1,000，m≤5,000。 对于 100% 的数据，保证 n≤200,000，m≤400,000。时间限制：10 sec 空间限制：256 MB 提示 [提示 1：真的可能有多种方案吗？] [提示 2：k 是否一定为 n-1 呢？（也就是说，选出的道路是否恰好构成了一棵树？）] [提示 3：这道题和最小生成树有什么关系呢？] 代码 #include <iostream> #include<vector> #pragma warning(disable:4996) using namespace std;
// ================= 代码实现开始 =================
/* 请在这里定义你需要的全局变量 */ int *Father;
int Find(int x)//查找某节点的根节点 { int fx;//某节点的根节点(父节点) if (Father[x] > 0)//若x的秩大于0，说明x不是根节点 { fx = Find(Father[x]);//若x不是根节点，则递归查找其根节点 Father[x] = fx;//*****此处至关重要，路径压缩，将某节点的父节点设置为根节点 ******** return fx; } else return x;//若x的秩小于等于0，说明x是根节点，返回x }
void Union(int x, int y)//将x和y所在的两个集合合并 { int fx = Find(x); int fy = Find(y); fy = fy;//断点调试点 if (fx == fy && fx != 0)//若fx和fy相等且其两个的秩不为0，则说明他们在同一个集合树中 return; if (Father[fx] < Father[fy]) Father[fy] = fx;//若x所在的集合树比较高，则将y所在的树合并到x所在的树中，即将y 的根节点设置为fx else if (Father[fx] == Father[fy])//若两个树的高度相等，则任意将一个树合并到另一个树中(此处是将x的根节点设置为fy) { Father[fy] -= 1;//合并后树的高度加一，故秩减一 Father[fx] = fy; } else//若y所在的集合树比较高，则将x所在的树合并到y所在的树中，即将x的根节点设置为fy Father[fx] = fy; }
// 给定一个n个点m条边的无向图，第i条边边权为i，求所有需要升级的边 // n：如题意 // m：如题意 // U：大小为m的数组，表示m条边的其中一个端点 // V：大小为m的数组，表示m条边的另一个端点 // 返回值：所有需要升级的边，从小到大排列；第一小问的答案自然即为返回值的size，所以你不必考虑如何返回size vector<int> getAnswer(int n, int m, vector<int> U, vector<int> V) { /* 请在这里设计你的算法 */
//通过生成最大生成树，我们即可知道哪一些道路应当升级为高速公路
Father = new int[n + 1]; for (int j = 0; j < n + 1; j++) { Father[j] = 0;//每个元素的初始秩为0 }
vector<int> Answer;//输出 Answer.reserve(200000);
int k = 0;//应升级为高速公路的k条道路，由最大生成树可知，当k=n-1时最大生成树生成完毕 for(int j=m;j>0;--j) { int u = U.back(); U.pop_back(); int v = V.back(); V.pop_back();
int fu = Find(u); int fv = Find(v); //下面用城市序号生成最大生成树 if (fu != fv || fu == 0)//若两个城市的 { Union(u, v); Answer.emplace_back(j);//将需要升级的道路序号压入容器中 k = k; k++; } if (k == n - 1) break; } return Answer; }
// ================= 代码实现结束 =================
int main() { int n, m; scanf("%d%d", &n, &m); vector<int> U, V; for (int i = 0; i < m; ++i) { int u, v; scanf("%d%d", &u, &v); U.emplace_back(u); V.emplace_back(v); } vector<int> ans = getAnswer(n, m, U, V); printf("%d\n", int(ans.size())); for (int i = int(ans.size())-1; i >= 0; --i)//由小到大输出道路序号 printf("%d\n", ans[i]); return 0; } |