最短路+二分题目整理

前往奥格瑞玛的道路

题目链接
\(\qquad\)题目要求最小化最大费用，显然是使用二分答案，二分答案首先应该看限制和目标，此处的限制是血量限制，而目标是费用目标。这种情况我们可以二分费用，然后在图上跑最短路判定血量是否满足。
\(\qquad\)对于check函数，我们去判定是否存在一条道路使得最高费用不超过mid，并且小号血量不超过hp，我们对于所有目的点费用不超过mid的点跑最短路，判定是否满足hp的限制即可。

代码

#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
using PII = pair<int, int>;

const int N = 1e5 + 10;
vector<PII> h[N];
int n, m, hp, hh, tt;
int cost[N], dist[N], st[N], q[N];

bool check(int mid) {
	if (cost[1] > mid) return 0;
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof dist);
	hh = tt = 0;
	q[0] = 1, st[1] = 1, dist[1] = 0;

	while (hh <= tt) {
		int t = q[hh ++ ];
		st[t] = 0;
		for (auto k : h[t]) {
			int v = k.first, w = k.second;
			if (cost[v] > mid) continue ;
			if (dist[v] > dist[t] + w) {
				dist[v] = dist[t] + w;
				if (!st[v]) st[v] = 1, q[ ++ tt] = v;
			}
		}
	}

	return dist[n] <= hp;
}

int main() {
	scanf("%d%d%d", &n, &m, &hp);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &cost[i]);
	while (m -- ) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		h[u].pb(v, w), h[v].pb(u, w);
	}

	int l = 0, r = 1e9 + 1;
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	if (r == 1e9 + 1) puts("AFK");
	else printf("%d\n", r);

	return 0;
}

Telephone Lines S

题目链接
\(\qquad\)我们可以取消 \(\le K\) 条道路的价值，并取得剩下的道路中最贵的。很容易想到一个贪心的策略，那就是取消最贵的 \(K\) 条路的价值，这样我们剩下的就是第 \(K + 1\) 贵的边了。
题目让我们最小化这个值，也就是让我们最小化 K + 1 大值，也可以采用二分。当然如果比它大的值小于 \(K\) 的时候，直接全部删除即可。
\(\qquad\)二分之前我们同样先看下限制和目标，这题的限制应该是更大值限制，而目标是最小费用目标，所以我们可以二分一下费用，并且判定是否在 \(1\sim N\)的路上有不超过 \(K\) 条边比它大即可。

代码

#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
using PII = pair<int, int>;

const int N = 1010;
vector<PII> h[N];
int n, m, k, st[N], dist[N];

bool check(int mid) {
	memset(dist, 0x3f, sizeof dist);
	memset(st, 0, sizeof st);
	queue<int> q;

	q.push(1), st[1] = 1, dist[1] = 0;
	while (q.size()) {
		int t = q.front();
		q.pop(), st[t] = 0;
		for (auto k : h[t]) {
			int v = k.first, w = k.second;
			int W = w > mid;
			if (dist[v] > dist[t] + W) {
				dist[v] = dist[t] + W;
				if (!st[v]) st[v] = 1, q.push(v);
			}
		}
	}

	return dist[n] <= k;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	while (m -- ) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		h[u].pb(v, w), h[v].pb(u, w);
	}

	int l = 0, r = 1e6 + 1;
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", r == 1e6 + 1 ? -1 : r);

	return 0;
}

Sightseeing Cows G

题目链接
\(\qquad\)这题是平均值最小问题，可以二分平均值，没有特殊的限定条件。
\(\large mid\le \frac{\sum w}{\sum t}\Rightarrow mid\times \sum t \le \sum w\Rightarrow mid\times \sum t - \sum w <= 0\)
所以我们是在原图上判负环和零环即可。

#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
using PII = pair<int, int>;

const int N = 1010;
vector<PII> h[N];
int n, m, st[N], f[N];
double dist[N];

bool dfs(int u, double mid) {
	st[u] = 1;
	for (auto k : h[u]) {
		int v = k.first, w = k.second;
		double W = w * mid - f[v];
		if (dist[v] >= dist[u] + W) {
			dist[v] = dist[u] + W;
			if (st[v]) { st[v] = 0; return 1; }
			if (dfs(v, mid)) { st[v] = 0; return 1; }
		}
	}
	return st[u] = 0;
}

bool check(double mid) {
	int ring = 0;
	memset(st, 0, sizeof st);
	for (int i = 1; i <= n; i ++ ) {
		if (ring) break ;
		if (st[i]) continue ;
		ring |= dfs(i, mid);
	}
	return ring;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &f[i]);
	while (m -- ) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		h[u].pb(v, w);
	}

	double l = 0, r = 1001;
	while (r - l > 1e-4) {
		double mid = (l + r) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}
	printf("%.2lf\n", r);

	return 0;
}

Word Rings

题目链接
\(mid\le \frac{\sum w}{cnt}\Rightarrow mid\times cnt\le \sum w\Rightarrow \sum (mid-w)\le 0\)
判一下零环和负环即可。
注意的是这里的建图方式。我们要求图上包含的信息是：点一定是给定字符串的头两个或尾两个字符；字符串的长度。我们由此可以想到只对于每个字符串连接首尾两个的字符，边权为字符串长度，然后与上题相同。

#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
using PII = pair<int, int>;

const int N = 1010;
vector<PII> h[N];
int n, m, st[N];
double dist[N];

bool dfs(int u, double mid) {
	st[u] = 1;
	for (auto k : h[u]) {
		int v = k.first, w = k.second;
		double W =  mid - w;
		if (dist[v] > dist[u] + W) {
			dist[v] = dist[u] + W;
			if (st[v]) { st[v] = 0; return 1; }
			if (dfs(v, mid)) { st[v] = 0; return 1; }
		}
	}
	return st[u] = 0;
}

bool check(double mid) {
	int ring = 0;
	memset(st, 0, sizeof st);
	for (int i = 1; i <= 676; i ++ ) {
		if (ring) break ;
		if (st[i]) continue ;
		ring |= dfs(i, mid);
	}
	return ring;
}

int main() {
	while (scanf("%d", &n), n) {
		for (int i = 1; i <= 676; i ++ ) h[i].clear();
		string s;
		for (int i = 1; i <= n; i ++ ) {
			cin >> s;
			int a, b, sz = s.size();
			a = (s[0] - 'a') * 26 + s[1] - 'a' + 1;
			b = (s[sz - 2] - 'a') * 26 + s[sz - 1] - 'a' + 1;
			h[a].pb(b, sz);
		}
		if (!check(0)) puts("No solution");
		else {
			double l = 0, r = 100001;
			while (l < r - 1e-5) {
				double mid = (l + r) / 2;
				if (check(mid)) l = mid;
				else r = mid;
			}
			printf("%.2lf\n", r);
		}
	}

	return 0;
}