prim，把每个墙看成一个节点，从起点用prim求最小生成树，直到覆盖到终点为止，输出最小生成树中的最大边
#include#include #include #include #include using namespace std;#define MAX_WALL_NUM 1005#define INF 0x3f3f3f3fstruct Wall{ int s, e, pos; bool h; //direction: is horizental}wall[MAX_WALL_NUM];int wall_num;double graph[MAX_WALL_NUM][MAX_WALL_NUM];void input(){ for (int i = 0; i < wall_num; i++) { int x, y, l; scanf("%d%d%d", &x, &y, &l); if (l < 0) { wall[i].h = false; swap(x, y); }else wall[i].h = true; wall[i].s = x; wall[i].e = x + abs(l); wall[i].pos = y; }}bool overlap(Wall a, Wall b){ if (a.s > b.e || a.e < b.s) return false; return true;}double cal(Wall a, Wall b){ if (a.h == b.h) { int dist1 = abs(a.pos - b.pos); if (overlap(a, b)) return dist1; else { int dist2 = min(abs(a.s - b.e), abs(a.e - b.s)); return sqrt(dist1 * dist1 + dist2 * dist2); } } if (a.s <= b.pos && a.e >= b.pos && b.s <= a.pos && b.e >= a.pos) return 0; if (a.s <= b.pos && a.e >= b.pos) return min(abs(b.s - a.pos), abs(b.e - a.pos)); if (b.s <= a.pos && b.e >= a.pos) return min(abs(a.s - b.pos), abs(a.e - b.pos)); int dist1 = min(abs(a.s - b.pos), abs(a.e - b.pos)); int dist2 = min(abs(b.s - a.pos), abs(b.e - a.pos)); return sqrt(dist1 * dist1 + dist2 * dist2);}void calculate_graph(){ for (int i = 0; i < wall_num; i++) { for (int j = i + 1; j < wall_num; j++) { graph[i][j] = graph[j][i] = cal(wall[i], wall[j]); } }}double prim(){ bool vis[MAX_WALL_NUM]; double dist[MAX_WALL_NUM]; memset(vis, 0, sizeof(vis)); fill(dist, dist + wall_num, INF); dist[0] = 0; double ret = 0; while (!vis[1]) { double min_dist = INF; int temp = -1; for (int i = 0; i < wall_num; i++) if (!vis[i] && dist[i] < min_dist) { temp = i; min_dist = dist[i]; } if (temp == -1) return -1; vis[temp] = true; dist[temp] = 0; ret = max(ret, min_dist); for (int i = 0; i < wall_num; i++) dist[i] = min(dist[i], dist[temp] + graph[temp][i]); } return ret;}int main(){ while (scanf("%d", &wall_num), wall_num) { input(); calculate_graph(); printf("%.2f\n", prim()); } return 0;}