【二分答案】SSL

【二分答案】SSL_1155 遨游

本文主要是介绍【二分答案】SSL_1155 遨游，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个图，上面有 $N$ 个省，每个省里面有一些城市，它们之间可能相连，其中每条路有个路费，每省里有一些优惠措施，可以让这个省的道路打一些折，不同的省之间的道路也有一些优惠措施。现在我们要求出 $L$ 和 $R$ ，让起点到终点的路的路费都在这个范围内，求出最大的 $L$ ，在这个基础上，求出最小的 $R$ 。

思路

根据题目我们很容易看出是一道二分题。
我们先二分 $L$ ，找到一个最大的，再在这个基础上二分到一个最小的 $R$ ，优惠预处理一下就好了。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#define clean for (int i = 1; i <= DN; i++) v[i] = 0
using namespace std;struct Edge{int x, y, next;double w;
}e[200001];
int N, M, S, T, DN, DM;
int L = 2147483647, R, l, r, ansl, ansr;
int c[50001], head[50001];
bool v[50001];void init() {scanf("%d %d", &N, &M);for (int i = 1; i <= M; i++) {DM++;scanf("%d %d %lf", &e[DM].x, &e[DM].y, &e[DM].w);e[DM].next = head[e[DM].x];head[e[DM].x] = DM;e[++DM].x = e[DM - 1].y;e[DM].y = e[DM - 1].x;e[DM].next = head[e[DM].x];head[e[DM].x] = DM;}int x, y;for (int i = 1; i <= N; i++) {scanf("%d", &x);for (int j = 1; j <= x; j++) {scanf("%d", &y);c[y] = i;DN++;}}int z[5001];for (int i = 1; i <= N; i++) scanf("%d", &z[i]);for (int i = 1; i <= DM; i+=2) {int x = e[i].x, y = e[i].y;if (c[x] == c[y]) e[i].w = e[i].w * z[c[x]] / 100.0;else e[i].w = e[i].w * (z[c[x]] + z[c[y]]) / 200.0;e[i + 1].w = e[i].w;if (L > e[i].w) L = e[i].w;if (R < e[i].w) R = e[i].w;}R++;scanf("%d %d", &S, &T);
}bool dfs(int p, int l, int r) {if (p == T) return 1;v[p] = 1;for (int i = head[p]; i; i = e[i].next) {if (!v[e[i].y] && e[i].w >= l && e[i].w <= r)if (dfs(e[i].y, l, r)) return 1; }return 0;
}void work() {l = L;r = R;while (l < r) {//Lint mid = (l + r) >> 1;clean;if (dfs(S, mid, R)) {//判断当前的答案能否满足起点能到达终点l = mid + 1;ansl = mid;}else r = mid;}l = ansl;r = R;while (l < r) {//Rint mid = (l + r + 1) >> 1;clean;if (dfs(S, ansl, mid)) {r = mid - 1;ansr = mid;}else l = mid;}printf("%d %d", ansl, ansr);
}
int main() {init();work();
}