前往奥格瑞玛的道路
题目链接
\(\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;
}