Codeforces 1005F Berland and the Shortest Paths 【最短路树】【性质】

Stella981
• 阅读 732

其实是一道裸题,如果没学过最短路树的话会比较难做,要想很久想到关键性质才能做出来。

最短路树顾名思义,就是从一个图中生成出来一棵树,使得每个顶点到root的距离是单源最短路。如果有这样的树的话,那可见这样的树是符合题意的。

怎么生成这样的树呢?关键在于记录前驱father,一个距离root最短路是6的点必定从一个距离root最短路是5的点到达(这两个点之间一定会有一条边)。所以我们对于所有顶点 2-n,每个顶点u我们找dis[u] = dis[v]+1的情况,这样的话v就是u的前驱。若v,u之间有一条边,那u到root的最短路就解决了【因为如果v到root的最短路不变,那u也不变】,原问题就变成了子问题,这就是这么建树 正确性的理解。

所有合法前驱记录完后,我们dfs下枚举所有前驱就可以了。【最多能生成father[2].size() * father[3].size() * ... * father[n].size()个合法答案】

 1 #include<iostream>
 2 #include<vector>
 3 #include<map>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 
 8 char comp[200005];
 9 vector< pair<int,int> > edge[200005];
10 vector<int> father[200005];
11 vector<string> ans;
12 int dis[200005],n,k;
13 queue< pair<int,int> > q;
14 
15 void dfs(int u){
16     if( ans.size()>=k ) return;
17     if(u==n+1) { ans.push_back(comp+1); return;}//建完了 
18     for(int i=0;i<father[u].size();i++){
19         comp[ father[u][i] ] = '1';//从众多前驱中挑一个
20         dfs(u+1);
21         comp[ father[u][i] ] = '0'; 
22     }
23 }
24 
25 int main(){
26     int m; cin>>n>>m>>k;
27     for(int i=1;i<=m;i++){
28         int u,v; scanf("%d %d",&u,&v);
29         edge[u].push_back( make_pair(v,i) );
30         edge[v].push_back( make_pair(u,i) );//建两条边 
31     }
32     
33     
34     memset(dis,-1,sizeof(dis));
35     for (int i = 1; i <= m; i++) comp[i] = '0';
36     //维护出dis数组
37     q.push( make_pair(1,0) ); dis[1]=0;
38     while(!q.empty()){
39         pair<int,int> pa = q.front(); q.pop();
40         int u=pa.first,d=pa.second;
41         for(int i=0;i<edge[u].size();i++){
42             int v=edge[u][i].first;
43             if( dis[v]==-1 ) {
44                 dis[v]=d+1;
45                 q.push( make_pair(v,d+1) );
46             } 
47         }
48     }
49     //找最短路数里每个顶点的前驱 
50     for(int i=2;i<=n;i++){
51         for(int j=0;j<edge[i].size();j++){
52             if( dis[i]==dis[ edge[i][j].first ]+1 ) father[i].push_back( edge[i][j].second );
53         }
54     }
55     
56     dfs(2);//从2开始建树 
57     if(ans.size()>=k){
58         cout<<k<<endl;
59         for(int i=0;i<k;i++) cout<<ans[i]<<endl;
60     }
61     else{
62         cout<<ans.size()<<endl;
63         for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
64     }
65     
66     
67     return 0;
68 }
点赞
收藏
评论区
推荐文章
Souleigh ✨ Souleigh ✨
3年前
Vue - diff 算法
diff是什么?diff就是比较两棵树,render会生成两颗树,一棵新树newVnode,一棵旧树oldVnode,然后两棵树进行对比更新找差异就是diff,全称difference,在vue里面diff算法是通过patch函数来完成的,所以有的时候也叫patch算法⏳diff发生的时机diff发生在什么时候呢?当然我们可以说在数据更新的时候发生d
zhenghaoz zhenghaoz
3年前
算法笔记:红黑树
红黑树,一种平衡二叉树,最为著名的应用就是CSTL中的map,是有序集合最为理想的存储方式之一。除了二叉树所具有的属性之后,红黑树中每个节点多了一个“颜色”属性,可以是红色或者是黑色。一棵红黑树应该满足一下的性质:1.每个节点是红色或者黑色的;2.根节点是黑色的;3.每个叶节点nil是黑色的(使用哨兵节点在删除调整时可以方便不少);4.如
Wesley13 Wesley13
3年前
Java实现 LeetCode 814 二叉树剪枝 (遍历树)
814\.二叉树剪枝给定二叉树根结点root,此外树的每个结点的值要么是0,要么是1。返回移除了所有不包含1的子树的原二叉树。(节点X的子树为X本身,以及所有X的后代。)示例1:输入:\1,null,0,0,1\输出:\1,null,0,null,1\解释:
Stella981 Stella981
3年前
Bellman
一、BellmanFordBellmanFord算法是一种用于计算带权有向图中单源最短路径(当然也可以是无向图)。与Dijkstra相比的优点是,也适合存在负权的图。若存在最短路(不含负环时),可用BellmanFord求出,若最短路不存在时,BellmanFord只能用来判断是否存在负环。松弛:    每次松弛操作
Wesley13 Wesley13
3年前
MySQL面试(二)
1、为什么索引遵循最左匹配原则?  当B树的数据项是符合的数据结构,比如(name,age,sex)的时候,B树是按照从左到右的顺序建立搜索树的。比如当(张三,20,F)这样的数据来检索的时候,b树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候
Stella981 Stella981
3年前
HDU 3416 Marriage Match IV (Dijkstra+最大流)
题意:N个点M条边的有向图,给定起点S和终点T,求每条边都不重复的ST的最短路有多少条。分析:首先第一步需要找出所有可能最短路上的边。怎么高效地求出呢?可以这样:先对起点S,跑出最短路;对于每条边e(u,v,w),若d\u\wd\v\。那么e就是最短路上的一条边。在前向星存储的图中遍历即可。网上还有题解用的方法是分别从S和T跑两
Wesley13 Wesley13
3年前
C语言递归之二叉树的最小深度
https://www.cnblogs.com/shichampion/p/12262678.html题目描述给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。示例输入:3,9,20,null,null,15,7
Wesley13 Wesley13
3年前
B
BTreeBTree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对23查找树的一种扩展。一个m阶的BTree有以下性质1.每个节点最多有m个子节点;2.每个非叶子节点(根节点除外)至少含有m/2个子节点;3.
Stella981 Stella981
3年前
HTML中offsetTop、clientTop、scrollTop、offsetTop各属性介绍
HTML精确定位:scrollLeft,scrollWidth,clientWidth,offsetWidth scrollHeight: 获取对象的滚动高度。 scrollLeft: 设置或获取位于对象左边界和窗口中目前可见内容的最左端之间的距离 scrollTop: 设置或获取位于对象最顶端和窗口中可见内容的最顶端之间的距离 
菜园前端 菜园前端
1年前
什么是树?
原文链接:什么是树?在生活中,大家对树肯定不陌生,小朋友都知道树不就是一类植物嘛,不管在任何地方都有各种各样的树。但是在计算机科学里面树是什么呢?一种分层数据的抽象模型,在我们前端工作中无处不在。在JavaScript中没有树这种数据结构,但是可以通过Ob