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

Codeforces Round 496 (Div. 3) F. Berland and the Shortest Paths

题目意思:有n个城市和m条道路数量,其中m > n - 1。从编号为 1的城市出发,可以沿着道路到达任何其他城市。选择n - 1条道路,使得1到所有城市的距离最短。如果选择方案数少于k,输出所有方案,否则输出k种方案。
这题可以看成一个以1为起点的bfs树,每个节点v需要从所有能作为其父节点的边里面选则一条,也就是dis[u] + 1 = dis[v]。不同的选择组合就是不同的答案。
由此我们先建图跑bfs,求每一个节点到1的最小距离,然后将所有能作为这个点父节点的点放入一个集合里面。

预处理代码
int n, m, k;
cin >> n >> m >> k;
vector <vector <int>> adj(n + 1);
vector <pll> edges(m + 1);
for(int i = 1; i <= m; i++){int u, v;cin >> u >> v;//用于查找可能父节点edges[i] = {u, v};//建图用于跑bfsadj[u].push_back(v);adj[v].push_back(u);
}
BFS
//求每一个级节点到1的最短距离
vector <int> dis(n + 1, INT_MAX);
dis[1] = 0;//初始化自身
queue <int> q;
q.push(1);//BFS
while(!q.empty()){int u = q.front();q.pop();//遍历u的子节点//由于bfs特性,每次扩散到的一定是最短的for(auto v : adj[u]){if(dis[v] == INT_MAX) {dis[v] = dis[u] + 1;q.push(v);}}
}

在得到每个点关于1的最短距离之后,我们现在可以将所有点和父节点相连的边的编号放入一个集合里面,方便我们选择。

加入集合
vector <vector <int>> fa(n + 1);
vector <vector <int>> fa(n + 1);
for(int i = 1; i <= m; i++){int u = edges[i].first, v = edges[i].second;//如果dis[u] = dis[v] + 1,说明v是u的父节点//反之,如果dis[v] = dis[u] + 1,说明u是v的父节点//将边的编号推入disif(dis[u] == dis[v] + 1) fa[u].push_back(i);if(dis[v] == dis[u] + 1) fa[v].push_back(i);
}

接下来是从所有可选的方式中选出k种,如果不足k种则选择所有。我们考虑枚举所有可能的组合,并将前k种存入结果数组ans里。

枚举
vector <int> idx (n + 1, 0); //当前第i个用了多少父节点
while(ans.size() < k){string s(m, '0');for(int v = 2; v <= n; v++){int ch = fa[v][idx[v]];  //对每个城市,从fa[v]选出第idx[v]个父边chs[ch - 1] = '1'; //将父边标记为'1';}ans.push_back(s); //保存当前结果bool have_use = false;for(int v = n; v >= 2; v--){if(idx[v] + 1 < fa[v].size()){idx[v]++;have_use = true; // 只要有一个没有枚举完,就不会停止break;} else idx[v] = 0;}if(!have_use) break;
}

最后输出结果

输出
cout << ans.size() << endl;
for(string t : ans) cout << t << endl;

AC代码

#include <bits/stdc++.h>
#define i64 long long
#define ui64 unsigned long long
#define pll pair<int, int>
using namespace std;void solve(){int n, m, k;cin >> n >> m >> k;vector <vector <int>> adj(n + 1);vector <pll> edges(m + 1);for(int i = 1; i <= m; i++){int u, v;cin >> u >> v;//用于查找可能父节点edges[i] = {u, v};//建图用于跑bfsadj[u].push_back(v);adj[v].push_back(u);}//求每一个级节点到1的最短距离vector <int> dis(n + 1, INT_MAX);dis[1] = 0;//初始化自身queue <int> q;q.push(1);//BFSwhile(!q.empty()){int u = q.front();q.pop();//遍历u的子节点//由于bfs特性,每次扩散到的一定是最短的for(auto v : adj[u]){if(dis[v] == INT_MAX) {dis[v] = dis[u] + 1;q.push(v);}}}vector <vector <int>> fa(n + 1);for(int i = 1; i <= m; i++){int u = edges[i].first, v = edges[i].second;//如果dis[u] = dis[v] + 1,说明v是u的父节点//反之,如果dis[v] = dis[u] + 1,说明u是v的父节点//将边的编号推入disif(dis[u] == dis[v] + 1) fa[u].push_back(i);if(dis[v] == dis[u] + 1) fa[v].push_back(i);}vector <string> ans;vector <int> idx (n + 1, 0); //当前第i个用了多少父节点while(ans.size() < k){string s(m, '0');for(int v = 2; v <= n; v++){int ch = fa[v][idx[v]];  //对每个城市,从fa[v]选出第idx[v]个父边chs[ch - 1] = '1'; //将父边标记为'1';}ans.push_back(s); //保存当前结果bool have_use = false;for(int v = n; v >= 2; v--){if(idx[v] + 1 < fa[v].size()){idx[v]++;have_use = true; // 只要有一个没有枚举完,就不会停止break;} else idx[v] = 0;}if(!have_use) break;}cout << ans.size() << endl;for(string s : ans) cout << s << endl;}signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;//cin >> t;while(t--)solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=33958

相关文章:

  • 《程序员修炼之道:从小工到专家》第五章读后感
  • 元推理框架,有机AI是天使
  • PWN手的成长之路-18_铁人三项(第五赛区)_2018_rop
  • Dotnet通过Http2解决CVE-2025-55315高危漏洞
  • 日志|JAVAWEB|YApi|vue-cli|VUE-Element
  • 20232401 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • FFT学习小结
  • OI 笑传 #20
  • 幂等的双倍快乐,你值得拥有
  • 2025.10.18——1黄
  • 10.18总结
  • 10.17总结
  • 软考中级学习总结(2)
  • 2025年粉末冶金制品/零件厂家推荐排行榜,高精度耐磨粉末冶金零件,优质粉末冶金制品公司推荐!
  • Neo4j 图数据库搭建和 Springboot 访问
  • 2025粉末冶金制品优质厂家推荐:鸿瑞粉末冶金,专业定制品质卓越!
  • AI元人文理论框架体系研究:价值原语化的文明演进机制与治理范式转变——声明Ai研究
  • 20251018
  • [buuctf]bjdctf_2020_router
  • AtCoder Beginner Contest 428 ABCDE 题目解析
  • 稻草火把下的星辰:回忆我的90年代求学路
  • 10月18日日记
  • 第九章-实战篇-运维杰克
  • AntennaPod - 开源Android播客管理器
  • 硬件基础知识
  • 第三章 权限维持-linux权限维持-隐藏
  • 第五章 linux实战-黑链
  • AI元人文:价值原语化——在创新与传承间搭建文明桥梁
  • Channel小结
  • 线段树历史值学习笔记