终于完成了第二章了，我要说的其实不是最后一个题，是我最后做的这一题，“Cow Tours”
/* ID: morgan_xww LANG: C TASK: cowtour */ /** 题目大意：有多个牧场(pasture)，由坐标(x,y)来定位，其中有些牧场之间有路， 表示两牧场是连通的，连通的若干个牧场称为牧区(field)，牧区的直径 定义为：牧区中任意两个牧场之间的最短距离的最大值。要求连通两个 牧场，这两个牧场分别属于两个不同的牧区，使得到的更大的新牧区的 直径最小，输出这个最小值。 解题：刚开始还以为只有两个牧区，结果错了，原来题目可能有多个牧区(至少两个)。 任意连通两个牧区，使新牧区直径最小。 我的思路是：先用Floyd算法更新一下邻接矩阵的最短路径，再找出有几个牧区，并且算出 每个牧区的直径，同时算出在同一个牧区中，每个牧场到其他牧场距离的最大值pst[i].dis。 最后遍历每一对牧场i,j,如果i,j属于不同的牧区，则他们组成的新牧区的直径 可能是这三种情况：i所属的牧区的直径;j所属的牧区的直径;pst[i].dis+distance(i,j)+pst[j].dis; 新牧区直径即为这三者中的最大值。刚开始我直接就把第三种情况当成了新牧区的直径， 没有想到老牧区的直径也可能是新牧区的直径 **/ #include <stdio.h> #include <math.h> #define INF 10000000000.0 int n; int fldNum; //记录牧区的数量 double map[151][151]; double fldDis[151]; //fldDis[i]表示i号牧区的直径 struct COORD { int x, y; //坐标 int fld; //该牧场所属牧区的编号 double dis; //在所属牧区中，该牧场到其他牧场距离的最大值 } pst[150]; //用结构体定义牧场(pasture). double Distance(struct COORD a, struct COORD b) //求两牧场之间距离的函数 { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } void Floyd() //Floyd算法求最短路径 { int i, j, k; for (k=0; k<n; k++) for (i=0; i<n; i++) for (j=0; j<n; j++) if (i != j && map[i][k]+map[k][j] < map[i][j]) map[i][j] = map[i][k]+map[k][j]; return ; } double Max(double a, double b, double c) //求三者最大值 { double t = (a > b ? a : b); return (t > c ? t : c); } int main() { freopen("cowtour.in", "r", stdin); freopen("cowtour.out", "w", stdout); int i, j, k; char c; double tmp, mindis; scanf("%d", &n); for (i=0; i<n; i++) scanf("%d %d", &pst[i].x, &pst[i].y); for (i=0; i<n; i++) { getchar(); for (j=0; j<n; j++) { scanf("%c", &c); if ('0' == c) map[i][j] = INF+10.0; else map[i][j] = Distance(pst[i], pst[j]); } } Floyd(); //计算每个牧场到所属牧区中的牧场距离的最大值 for (i=0; i<n; i++) { pst[i].dis = 0.0; for (j=0; j<n; j++) { if (map[i][j]<INF && map[i][j]>pst[i].dis) pst[i].dis = map[i][j]; } } //找出牧区的数量，并计算每个牧区的直径 fldNum = 1; for (i=0; i<n; i++) { if (pst[i].fld > 0) continue; pst[i].fld = fldNum; tmp = pst[i].dis; for (j=i+1; j<n; j++) { if (map[i][j] < INF) { pst[j].fld = fldNum; if (pst[j].dis > tmp) tmp = pst[j].dis; } } fldDis[fldNum] = tmp; fldNum++; } //找出连接两个牧区后所得新牧区的最小直径 mindis = INF; for (i=0; i<n; i++) { for (j=i+1; j<n; j++) { if (pst[i].fld == pst[j].fld) continue; //两个牧场属于同一个牧区 tmp = Distance(pst[i], pst[j])+pst[i].dis+pst[j].dis; tmp = Max(tmp, fldDis[pst[i].fld], fldDis[pst[j].fld]); if (tmp < mindis) mindis = tmp; } } printf("%.6lf/n", mindis); exit(0); }