CCF--第四题，第一次小汇总.pdf

CCF--第四题，第一次小汇总--第1页 CCF--第四题，第⼀次⼩汇总 　　第四题⼀般为⽐较基础的图论，不会太难，但也不会让你做得太舒服，关键是找到模型然后稍微变通下（这⾥的变通还挺考验对图论中 ⼀些基本模型的理解的）。 　　简化题⽬的意思，寻找模型，图论有许多的算法，很多时候并不是不会写，⽽是没有简化出模型，不知⽤何算法。 　　同时注意计算结果的范围是否会爆int。 　　复杂度计算（有些题其实可以⽆脑爆搜），⼀般1s的运算量为10^8. 　　which means: = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 2014 CCF--第四题，第一次小汇总--第1页 CCF--第四题，第一次小汇总--第2页 问题描述 　　⽬前在⼀个很⼤的平⾯房间⾥有 n 个⽆线路由器,每个⽆线路由器都固定在某个点上。任何两个⽆线路由器只要距离不超过 r 就能互相建⽴⽹络连接。 　　除此以外,另有 m 个可以摆放⽆线路由器的位置。你可以在这些位置中选择⾄多 k 个增设新的路由器。 　　你的⽬标是使得第1 个路由器和第2 个路由器之间的⽹络连接经过尽量少的中转路由器。请问在最优⽅案下中转路由器的最少个数是多少? 输⼊格式 　　第⼀⾏包含四个正整数 n,m,k,r 。(2 ≤ n ≤ 100,1 ≤ k ≤ m ≤ 100, 1 ≤ r ≤ 108)。 　　接下来 n ⾏,每⾏包含两个整数 xi 和 yi,表⽰⼀个已经放置好的⽆线路由器在 (xi, yi) 点处。输⼊数据保证第1 和第2 个路由器在仅有这 n 个路由器的情 况下已经可以互相连接(经过⼀系列的中转路由器)。 　　接下来 m ⾏,每⾏包含两个整数 xi 和 yi,表⽰ (xi, yi) 点处可以增设⼀个路由器。 　　输⼊中所有的坐标的绝对值不超过108,保证输⼊中的坐标各不相同。 输出格式 　　输出只有⼀个数,即在指定的位置中增设 k 个路由器后,从第 1 个路由器到第2 个路由器最少经过的中转路由器的个数。 样例输⼊ 5 3 1 3 0 0 5 5 0 3 0 5 3 5 3 3 4 4 3 0 样例输出 2 201403-4⽆线⽹络题⾯ 　　⽐较早年的第四题，所以题⽬还是⽐较简单的，之后会发现许多都是版⼦。这道题我们先简化⼀下题⽬的意思：(n+m)个点，每步步长 限制为r，求从1点到2点的最⼩步数~。(吐槽⼀下这⾥题⽬中把n个点和m个点分开了，故弄⽞虚，考试的话要清醒呀)。简化题⽬意思后能 较为清晰地发现这就是⼀道搜索题，⼀下⼦蹦出两种思路bfs，dfs。 BFS CCF--第四题，第一次小汇总--第2页 CCF--第四题，第一次小汇总--第3页 struct Node { int id, step; Node( int a, int b): id(a), step(b) {} }; inline boo can_go( const x1,const y1, const x2, const y2) { if((x1 - x2) maxr || (x1 - x2) -maxr) return false ; if((y1 - y2) maxr || (y1 - y2) -maxr) return false ; if(((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) maxr*maxr) return false ; return true ; } int bfs( int s) { queueNode q; while(q.size()) q.pop(); q.push(Node(s, 0)); vis[s] = true ; while(q.size()) { Node u = q.front(); q.pop(); int id = u.id; if(id == 2) return u.step- 1; //减去终点才是中间的点 for (int i=1; i=n+m; ++i) { if(vis[i]) continue ;