[//]: # (推荐题解模板，请替换blablabla等内容 ^^) [https://vjudge.net/contest/430497#problem/B](https://) ### 题目描述 Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping. Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence. The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones. You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone. blablabla ### 说白了 就是找青蛙所有 跳跃方案中的最长的跳跃范围 再在 所有的方案中进行比较 找最小的 ### 最小的最长 ### 最长 具体怎么去修改 也要把 样例进行带入 #### 样例 Sample Input 2 0 0 3 4 3 17 4 19 4 18 5 0 Sample Output Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414 ``` blablabla ``` ---------- ### 算法1 ##### (暴力枚举) $O(n^2)$ blablabla #### 时间复杂度 #### 参考文献 #### C++ 代码 ``` #include #include #include #include #include #include using namespace std; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; typedef pair PII; PII a[maxn]; int h[maxn], ne[maxn], e[maxn], idx; double w[maxn],dis[maxn]; bool book[maxn];int n; void add(int u ,int v,double ww) { e[idx] = v; w[idx] = ww; ne[idx] = h[u]; h[u] = idx ++; } void SPFA() // 最小 最长 { //先把起点进队 最长里边找最下的 for(int i = 1 ; i <= n ; i ++) dis[i] = INF; memset(book, false , sizeof(book)); queue alls;// alls.push(1); dis[1] = 0; book[1] = true; // printf("%f",dis[2]); while(!alls.empty()) { int t = alls.front(); alls.pop(); book[t] = false; for(int i = h[t] ; i != -1; i =ne[i]) { int v = e[i];//printf("%f\n",dis[v]); if(dis[v] > max(dis[t] , w[i])) { dis[v] = max(dis[t] , w[i]); if(!book[v]) { book[v] = true; alls.push(v); } } } } } int main() { int cnt = 1; while(scanf("%d", &n) != EOF) { if(n == 0) break; idx = 0; memset(h ,-1, sizeof(h)); memset(a, 0 ,sizeof(a)); for(int i = 1 ; i <= n ; i ++) { int x, y; scanf("%d %d", &x, &y); a[i] = {x, y}; } for(int i = 1 ; i <= n ;i ++) { for(int j = 1 ; j <= n ; j ++) { int x1 = a[i].first, y1 = a[i].second; int x2 = a[j].first, y2 = a[j].second; double cc = sqrt(1.0 *(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) * 1.0); if(i != j) { add(i,j,cc); add(j,i,cc); } } } SPFA(); printf("Scenario #%d\n",cnt ++); printf("Frog Distance = %.3f\n\n",dis[2]); } return 0; } ``` ---------- ### [https://vjudge.net/contest/430497#problem/C](https://) ##### 题目描述 Background Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight. Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know. Problem You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo's place) to crossing n (the customer's place). You may assume that there is at least one path. All streets can be travelled in both directions. Sample Input 1 3 3 1 2 3 1 3 4 2 3 5 Sample Output Scenario #1: 4 #### 题目说白了 就是找 当前每种方案走到终点 最小承载量（不能超过所走路的最大承载量） 再在所有方案中找到最大的 ### 最大的最下 #### 具体怎么去修改 最小 然后 把当前样例代入 #### C++ 代码 ``` #include #include #include #include #include //变种 最小里边找最大的 using namespace std; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; int h[maxn], ne[maxn], e[maxn], w[maxn], dis[maxn], idx; bool book[maxn]; int n, m; void add(int u , int v, int ww) { e[idx] = v; w[idx] = ww; ne[idx] = h[u]; h[u] = idx ++; } void SPFA() { memset(book, false, sizeof(book)); memset(dis, 0, sizeof(dis)); queue alls; //先把起点进队 alls.push(1); dis[1] = INF; // book[1] = true; // while(!alls.empty()) { int t = alls.front(); alls.pop(); book[t] = false; for(int i = h[t]; i != -1 ; i = ne[i]) { int v = e[i]; if(dis[v] < min(dis[t] ,w[i])) // dis[v] < min(dis[t], w[i]) { dis[v] = min(dis[t] , w[i]); if(!book[v]) { book[v] = true; alls.push(v); } } } } } int main() { int T; cin >> T; int i = 1; while(T --) { scanf("%d%d", &n, &m); memset(h, -1, sizeof(h)); // memset(ne, 0 ,sizeof(ne)); // memset(w, 0 ,sizeof(w)); // memset(e, 0, sizeof(e)); idx = 0; for(int i = 1 ; i <= m ; i ++) { int x, y, z; scanf("%d %d %d", &x, &y, &z); add(x, y, z); add(y,x, z); } SPFA(); printf("Scenario #%d:\n", i ++); printf("%d\n\n", dis[n]); } return 0; } ``` ### >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>重 ### [https://vjudge.net/contest/434441#problem/A](https://) ### 题目描述 题目说白了 要求 第（k + 1)大的边的 最小长度 ### 最小的第（k+1）大的边 ### 可以发现 根据以上两种变形 无法解答 ### 进而去 考虑 二分枚举答案 然后检验 二分正确性 ### 然后我们会发现 假设 res 恰好 为 mid 时 恰好比当前长的大的边为k条 那么答案是最优解的 ### 右移 那么 比当前长度大的边 肯定 <= k 不是我们的最优解 比最优解 大 ### 左移 那么 比当前长度大的边 肯定 >= k 我们的答案就是不合法的 因为最少花费为 第（k+1)大的边 Description FarmerJohn打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司 支付一定的费用。FJ的农场周围分布着N(1<=N<=1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间 都没有电话线相连。一共P(1<=P<=10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为L_i(1<=L_i<=1,000,000)。数据中保证每对{A_i，B_i }最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线 杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话 网络。经过谈判，电信公司最终同意免费为FJ连结K(0<=K #include #include #include #include using namespace std; const int INF = 0x3f3f3f3f; const int maxn = (1e4 + 10) * 2; struct note{ int v; int w; int ne; }edge[maxn]; int h[1010], dis[1010], idx; bool book[1010]; int N, P , K; void add(int u ,int v, int w) { edge[idx].v = v; edge[idx].w = w; edge[idx].ne = h[u]; h[u] = idx ++; } bool check(int mid)//计算比mid大的 1-- N有多少条边 { memset(dis,INF, sizeof(dis)); memset(book, false,sizeof(book)); queue alls;//先把起点 进队 alls.push(1); dis[1] = 0; book[1] = true; while(!alls.empty()) { int t = alls.front(); alls.pop(); book[t] = false; for(int i = h[t]; i != -1; i = edge[i].ne) { int v = edge[i].v; if(dis[v] > dis[t] + (edge[i].w > mid)) { dis[v] = dis[t] + (edge[i].w > mid); if(!book[v]) { book[v] = true; alls.push(v); } } } } return dis[N] <= K; } int main() { scanf("%d %d %d", &N, &P, &K); memset(h, -1, sizeof(h)); for(int i = 1 ; i <= P ; i ++) { int a ,b, c; scanf("%d %d %d", &a, &b, &c); add(a, b, c), add(b, a, c); }// r = mid l = mid + 1 int l = 0, r = 1e6 + 1; while(l < r) // 右区间 r = mid l = mid + 1 { int mid = (l + r) >> 1; if(check(mid)) r = mid; else l = mid + 1; } if(l == 1e6 + 1) { printf("-1\n"); } else { printf("%d\n",l); } return 0; } ```