dq;dq.push_back(1);while (dq.size()) {int u = dq.front(); dq.pop_front();if (u == N) break;if (vis[u]) continue;vis[u] = true;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];int cost = (w[i] > x);if (d[v] >= d[u] + cost) {d[v] = d[u] + cost;if (cost) dq.push_back(v);else dq.push_front(v);}}}return d[N] <= K;}int main() {memset(h, -1, sizeof h);scanf("%d%d%d", &N, &M, &K);for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);add(b, a, c);}int lb = -1, ub = 1000010;while (ub - lb > 1) {int mid = (lb + ub) / 2;if (bfs(mid)) ub = mid;else lb = mid;}if (ub > 1000000) printf("-1\n");else printf("%d\n", ub);return 0;}
01分数规划
指的是在图论里面，一堆值之和与另一堆值之和的比值最大，这一般称为01分数规划问题，通常可以用二分去写 。
3. 361. 观光奶牛
#include#include#include#includeusing namespace std;const int maxn = 1010, maxm = 5010;int h[maxn], w[maxm], ver[maxn], e[maxm], ne[maxm], idx;int N, M, cnt[maxn];double d[maxn];bool vis[maxn];void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;}bool C(double x) {queue que;memset(cnt, 0, sizeof cnt);for (int i = 1; i <= N; i++) {que.push(i);vis[i] = true;}while (que.size()) {int u = que.front(); que.pop();vis[u] = false;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] < d[u] + ver[v] - x * w[i]) {d[v] = d[u] + ver[v] - x * w[i];cnt[v] = cnt[u] + 1;if (cnt[v] >= N) return true;if (!vis[v]) {que.push(v);vis[v] = true;}}}}return false;}int main() {memset(h, -1, sizeof h);scanf("%d%d", &N, &M);for (int i = 1; i <= N; i++) scanf("%d", &ver[i]);for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}double lb = 0, ub = 1000;while(ub - lb > 1e-4) {double mid = (lb + ub) / 2;if (C(mid)) lb = mid;else ub = mid;}printf("%.2f\n", lb);return 0;}
4. 1165. 单词环
#includeusing namespace std;const int maxn = 700, maxm = 100010;int h[maxn], w[maxm], e[maxm], ne[maxm], idx;char edge[1010];bool vis[maxn];int N, M;double d[maxn];map, int> id;void init() {string ver("__");for (int i = 'a'; i <= 'z'; i++) {for (int j = 'a'; j <= 'z'; j++) {ver[0] = i, ver[1] = j;id[ver] = N++;}}}void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;}bool C(double x) {queue que;for (int i = 0; i < N; i++) {que.push(i);vis[i] = true;}int cnt = 0;while (que.size()) {if (++cnt > 10000) return true;int u = que.front(); que.pop();vis[u] = false;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] < d[u] + w[i] - x) {d[v] = d[u] + w[i] - x;if (!vis[v]) {que.push(v);vis[v] = true;}}}}return false;}int main() {init();string st("__"), ed("__");while (scanf("%d", &M) && M) {memset(h, -1, sizeof h);idx = 0;for (int i = 0; i < M; i++) {scanf("%s", edge);int len = strlen(edge);if (len < 2) continue;st[0] = edge[0], st[1] = edge[1];ed[0] = edge[len - 2], ed[1] = edge[len - 1];int a = id[st], b = id[ed];add(a, b, len);}double lb = 0, ub = 1000;while (ub - lb > 1e-6) {double mid = (lb + ub) / 2;if (C(mid)) lb = mid;else ub = mid;}if(fabs(lb) < 1e-3) printf("No solution\n");else printf("%f\n", lb);}return 0;}
5. 1125. 牛的旅行
#include#include#includeusing namespace std;const int maxn = 160;const double INF = 1e9, EPS = 1e-3;int N;double x[maxn], y[maxn], d[maxn][maxn], max_d[maxn], ans = INF;char g[maxn][maxn];bool equal(double x, double y) {return fabs(x - y) <= EPS;}double dis(double x1, double y1, double x2, double y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));}void floyd() {for (int i = 0; i < N; i++) fill(d[i], d[i] + N, INF);for (int i = 0; i < N; i++) {d[i][i] = 0;for (int j = 0; j < i; j++) {if (g[i][j] == '1') d[i][j] = d[j][i] = dis(x[i], y[i], x[j], y[j]);}}for (int k = 0; k