USACO 2.4.3 Cow Tours 解题报告

这个题目涉及的算法真的好多好多，一下子还真摸不着头脑，但摸着没摸着都先听我说。 首先要把链接在一起的那些牧区之间的距离算出来（勾股定理），然后要把各个牧场的牧区标示出来（洪水填充），这样就能进行下一步了，再把各个节点之间的距离算出来，用floyd-warshall算法，O(n^3)的那个算法，然后，再把每个牧区在这个牧场距离最远的节点之间的距离算出来，再把每个牧场的直径算出来，这题目就大概出来了。 最后在循环两个牧区，如果是在一个牧场就退出循环，如果是在两个不同的牧场的话，那如果连接起来这个新的牧场的直径就有三种可能：a牧区所在的牧场的直径；b牧区所在的牧场的直径；a牧区在牧场中距离最远的距离加上b牧区在牧场中距离最远的距离再加上a，b之间的距离。 代码如下： / LANG: C ID: yylogoo1 PROG: cowtour / #include $\#include\#define\; INF\; 1000000.0\; int\; x[150],\; y[150];\; double\; map[150][150];\; int\; group[150];\; int\; n;\; double\; getdis(int\; i,\; int\; j)\; \{\; return\; sqrt((x[i]\; -\; x[j])$ (x[i] - x[j]) + (y[i] - y[j]) (y[i] - y[j])); } void fool(int a, int k) { int i; if(group[a]){ return; } group[a] = k; for(i = 0; i b ? a : b; } int main(void) { int i, j, k; int ch; double max, t; freopen("cowtour.in", "r", stdin); freopen("cowtour.out", "w", stdout); scanf("%d\n", &n); for(i = 0; i map[i][k] + map[k][j]){ map[i][j] = map[i][k] + map[k][j]; } } } } for(i = 0; i