hihoCoder 1139-二分·二分答案
#1139 : 二分·二分答案
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在上一回和上上回里我们知道Nettle在玩《艦これ》，Nettle在整理好舰队之后终于准备出海捞船和敌军交战了。
在这个游戏里面，海域是N个战略点(编号1..N)组成，如下图所示
其中红色的点表示有敌人驻扎，猫头像的的点表示该地图敌军主力舰队(boss)的驻扎点，虚线表示各个战略点之间的航线(无向边)。
在游戏中要从一个战略点到相邻战略点需要满足一定的条件，即需要舰队的索敌值大于等于这两点之间航线的索敌值需求。
由于提高索敌值需要将攻击机、轰炸机换成侦察机，舰队索敌值越高，也就意味着舰队的战力越低。
另外在每一个战略点会发生一次战斗，需要消耗1/K的燃料和子弹。必须在燃料和子弹未用完的情况下进入boss点才能与boss进行战斗，所以舰队最多只能走过K条航路。
现在Nettle想要以最高的战力来进攻boss点，所以他希望能够找出一条从起始点(编号为1的点)到boss点的航路，使得舰队需要达到的索敌值最低，并且有剩余的燃料和子弹。
特别说明：两个战略点之间可能不止一条航线，两个相邻战略点之间可能不止一条航线。保证至少存在一条路径能在燃料子弹用完前到达boss点。
提示：你在找什么？
输入
第1行：4个整数N,M,K,T。N表示战略点数量，M表示航线数量，K表示最多能经过的航路，T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000
第2..M+1行：3个整数u,v,w，表示战略点u,v之间存在航路，w表示该航路需求的索敌值，1≤w≤1,000,000。
输出
第1行：一个整数，表示舰队需要的最小索敌值。
样例输入
5 6 2 5
1 2 3
1 3 2
1 4 4
2 5 2
3 5 5
4 5 3
样例输出
3
本题的目标是在无向图中，求从点1到T的路径中的索敌值的最大值的最小值，且经过的路径不能超过k段。 在输入的时候，我们能得到所有索敌值的最大值high和最小值low，high值显然能够成功到达T点，且不超过k段，因为题目说了保证至少存在一条路径能在燃料子弹用完前到达boss点；low就不一定了。所以二分答案的意思就是在区间[low,high]中二分查找最小可行解。 假设函数f(x)能判断当索敌值为x时，是否能成功到达T点且不超过k段。则每二分一次就求一次f(mid)，根据f(mid)的值调整区间[low,high]的端点。所以现在的关键就是函数f(x)。 f(x)可以使用广度优先搜索实现。实现的时候注意不能使用邻接矩阵保存图，有可能TLE或MLE，使用邻接表更好。完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<queue> #include<vector> using namespace std; const int kMaxN = 10005, kINF = 0x3f, kMaxW = 1000005; vector<vector<int>> path; vector<vector<int>> powers; vector<bool> visit; int n, m, k, t; bool BFS(int power) { visit.clear(); visit.resize(n + 1, false); queue<int> Q; int u, v, len = 0;; Q.push(1); visit[1] = true; Q.push(-1); while (!Q.empty()&&len<k) { u = Q.front(); Q.pop(); if (u == -1) { if (Q.empty()) return false; else { len++; Q.push(-1); continue; } } for (int i = 0; i < path[u].size(); i++) { v = path[u][i]; if (!visit[v]&&powers[u][i] <= power) { if (v == t) return true; visit[v] = true; Q.push(v); } } } return false; } int main() { freopen("input.txt", "r", stdin); scanf("%d %d %d %d", &n, &m, &k, &t); path.resize(n + 1); powers.resize(n + 1); int u, v, w, low = kMaxW, high = 0; for (int i = 0; i < m; i++) { scanf("%d %d %d", &u, &v, &w); low = min(low, w); high = max(high, w); path[u].push_back(v); path[v].push_back(u); powers[u].push_back(w); powers[v].push_back(w); } while (low+1 < high) { int mid = (low + high) / 2; if (BFS(mid)) high = mid; else low = mid; } printf("%d\n", high); return 0; } [/cpp] 在BFS的时候可以单独保存每个点及该点此时的深度(len)，也可以共用一个len，只需额外加入一个标记-1，当碰到-1时，说明已经遍历完一层了，深度加1。 本代码提交AC，用时189MS，内存8MB。]]>