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,使用邻接表更好。完整代码如下:

#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;
}

在BFS的时候可以单独保存每个点及该点此时的深度(len),也可以共用一个len,只需额外加入一个标记-1,当碰到-1时,说明已经遍历完一层了,深度加1。

本代码提交AC,用时189MS,内存8MB。

Leave a Reply

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