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