题目意思:有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;
}