分析：這道題實在是不好想，一個可以騙分的想法是假定要求的那個點在中心點上,可以騙得不少分.但是在邊上的點要怎么確定呢？理論復雜度O(﹢無窮).答案一定是和端點有關的，涉及到最大值最小，考慮二分最大值，關鍵就是怎么check.如果有一條邊x,還有一個點y,把y到x上的點的距離>mid的點給標記上，這樣就會形成許多個區間，判斷一下x是否被這些區間給完全覆蓋住了，如果沒有被完全覆蓋住，證明這個最大值可以更小.思路非常奇妙,具體實現細節可以參看代碼:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int maxn = 210, maxm = 40010;int n, m, a[maxn][maxn], head[maxn], to[maxm],ans,len,top,nextt[maxm],w[maxm], tot = 1; struct node {int x, y, z; }e[20000];struct node2 {int first, second; }e2[20000];void add(int x, int y, int z) {w[tot] = z;to[tot] = y;nextt[tot] = head[x];head[x] = tot++; }void floyd() {for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (a[i][j] > a[i][k] + a[k][j])a[i][j] = a[i][k] + a[k][j]; }void add2(int x, int y) {e2[++top].first = x;e2[top].second = y; }bool cmp(node2 a, node2 b) {if (a.first == b.first)return a.second < b.second;return a.first < b.first; }bool can() {int x = 0;sort(e2 + 1, e2 + 1 + top,cmp); for (int i = 1; i <= top; i++){if (x < e2[i].first)return false;if (x > e2[i].second)continue;x = e2[i].second + 1;}if (x > len)return true;return false; }bool check(int p) {bool flag = false;for (int i = 1; i <= m; i++){top = 0;len = e[i].z;for (int j = 1; j <= n; j++){int x = p - a[e[i].x][j];int y = p - a[e[i].y][j];if (x < 0 && y < 0){add2(0, e[i].z);break;}if (x >= e[i].z || y >= e[i].z)continue;if (x + y >= e[i].z)continue;add2(max(0, x + 1), min(e[i].z, e[i].z - y - 1));}if (!can())flag = 1;if (flag)break;}if (flag)return true;return false; }int main() {memset(a, 127 / 3, sizeof(a)); scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++){int u, v, z;scanf("%d%d%d", &u, &v, &z);z *= 2;add(u, v, z);add(v, u, z);e[i].x = u;e[i].y = v;e[i].z = z;a[u][v] = a[v][u] = min(a[u][v], z);}for (int i = 1; i <= n; i++)a[i][i] = 0;floyd();int l = 0, r = 10000010;while (l <= r){int mid = (l + r) >> 1;if (check(mid)){ans = mid;r = mid - 1;}elsel = mid + 1;}double temp = ans / 2.0;printf("%.2lf\n", temp); return 0; }
?
)
