首页 > 代码库 > HDU 3832 Earth Hour
HDU 3832 Earth Hour
题意:
平面上有一些圆 要求用最少的圆将1、2、3点连通 这三点上的圆必须使用
思路:
如果两圆可以连通 则用边把它们圆心相连 然后问题转化为图论模型 那么我们只需要从1、2、3求出到其他点的最短路 再枚举中间点分别到这三个点距离和即可
为什么这样找中间点是对的?? 因为虽然可能存在x->1和x->2的最短路经过y 但是如果y真的存在 那么最小值一定是y提供的 就算我们用x计算出错误的答案 它也不会是最后的答案
代码:
#include<stdio.h> #define N 205 #define inf 100000 int t, n, ans; int x[N], y[N], r[N], maz[N][N], dis[5][N], vis[N]; int min(int ff, int gg) { if (ff < gg) return ff; return gg; } void dij(int s) { int i, j, p, f; for (i = 1; i <= n; i++) { dis[s][i] = inf; vis[i] = 0; } dis[s][s] = 0; for (i = 1; i <= n; i++) { f = inf; for (j = 1; j <= n; j++) { if (!vis[j] && dis[s][j] < f) { f = dis[s][j]; p = j; } } vis[p] = 1; for (j = 1; j <= n; j++) { if (!vis[j] && maz[p][j] != inf && dis[s][j] > dis[s][p] + maz[p][j]) dis[s][j] = dis[s][p] + maz[p][j]; } } } int main() { int i, j; scanf("%d", &t); while (t--) { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d%d%d", &x[i], &y[i], &r[i]); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= (r[i] + r[j]) * (r[i] + r[j])) maz[i][j] = 1; else maz[i][j] = inf; } maz[i][i] = 0; } for (i = 1; i <= 3; i++) dij(i); ans = inf; for (i = 1; i <= n; i++) { ans = min(ans, dis[1][i] + dis[2][i] + dis[3][i]); } if (ans == inf) printf("-1\n"); else printf("%d\n", n - ans - 1); } return 0; }
HDU 3832 Earth Hour
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。