hihoCoder 1139-二分·二分答案

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。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *