好坑啊，居然还有直径不通过新边的数据，还好不是很多。
注意一定要等Floyd跑完之后再去找连通块的直径，不然一定是INF。
#include#include #include #include using namespace std;int pre[155];void init(int n) { for(int i = 0; i < n; ++i) pre[i] = i;}double D[155];int find(int x) { return pre[x] == x ? x : pre[x] = find(pre[x]);}void unit(int x, int y) { int fx = find(x), fy = find(y); if(!(fx == fy)) pre[fx] = fy;}bool iscc(int x, int y) { return find(x) == find(y);}double pos[155][2];double dis_t[155][155];double dist(int i, int j) { return sqrt((pos[i][0] - pos[j][0]) * (pos[i][0] - pos[j][0]) + (pos[i][1] - pos[j][1]) * (pos[i][1] - pos[j][1]));}int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku init(150); int n; cin >> n; for(int i = 0; i < n; ++i) cin >> pos[i][0] >> pos[i][1]; char ch; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) dis_t[i][j] = 1e9; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) { cin >> ch; if(ch == '1') { unit(i, j); dis_t[j][i] = dis_t[i][j] = dist(i, j); } if(i == j) dis_t[i][j] = 0; } for(int k = 0; k < n; ++k) for(int j = 0; j < n; ++j) for(int i = 0; i < n; ++i) { if(iscc(i, j)) { dis_t[i][j] = min(dis_t[i][j], dis_t[i][k] + dis_t[k][j]); } } double max_dis[155] = {}; for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ if(iscc(i, j)){ max_dis[i] = max(max_dis[i], dis_t[i][j]); } } D[find(i)] = max(D[find(i)], max_dis[i]); } double minn = 1e9; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) if(!iscc(i, j)) { minn = min(minn, max(max(D[find(i)], D[find(j)]), dist(i, j) + max_dis[i] + max_dis[j])); } /*char s[20005]; sprintf(s,"%.8f\n", minn); int pi=0; for(pi=0;s[pi]!='.';++pi); s[pi+7]='\0'; puts(s);*/ printf("%.6f\n", minn); return 0;}