Solve

USACO 2.3.3 Cowtour

题目解答

这道题目是图论问题，首先用floyd求出每对点的最短路，然后再找出单独每个点的可连接的最远的点(直径)，接下来就是计算两个分离牧区的直径。首先遍历所有不连通的点对，然后用这两点的距离加上两点原来的直径。如果更小，则更新直到结束。
但是还有一种特殊情况：“包含”。如果一个牧场恰好包含另一个，且大的牧场直径比计算出的要长一些，则结果应该是更大的那个才对。(参考图片：红色表示最终连接的结果，蓝色表示大牧场的直径，显然蓝色的才正确)

USACO 2.3.4

运行结果

Compiling…
Compile: OK
Executing…
Test 1: TEST OK [0.022 secs, 3108 KB]
Test 2: TEST OK [0.011 secs, 3108 KB]
Test 3: TEST OK [0.000 secs, 3108 KB]
Test 4: TEST OK [0.011 secs, 3108 KB]
Test 5: TEST OK [0.043 secs, 3108 KB]
Test 6: TEST OK [0.032 secs, 3108 KB]
Test 7: TEST OK [0.032 secs, 3108 KB]
Test 8: TEST OK [0.065 secs, 3108 KB]
Test 9: TEST OK [0.054 secs, 3108 KB]
All tests OK.
YOUR PROGRAM (‘cowtour’) WORKED FIRST TIME! That’s fantastic
– and a rare thing. Please accept these special automated
congratulations.

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<fstream>
#include<cmath>
using namespace std;
ofstream fout ("cowtour.out",ios::out);
ifstream fin ("cowtour.in",ios::in);
const double maxn=1000000000;
double map[151][151],pos[151][2],dmap[151],dis=maxn,temp;
long n;
int main()
{
  char te;
  fin>>n;
  for(int i=1;i<=n;i++) fin>>pos[i][0]>>pos[i][1];
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
      fin>>te;
      if(te=='1' ) map[i][j]=sqrt(pow(pos[i][0]-pos[j][0],2)+pow(pos[i][1]-pos[j][1],2));
      else map[i][j]=maxn;
    }
    
    for(int k=1;k<=n;k++)  //连通图,floyd
      for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
             if(i!=j) map[i][j]=((map[i][k]+map[k][j]<map[i][j])?map[i][k]+map[k][j]:map[i][j]);
                 
    for(int i=1;i<=n;i++)//自身的最大距离
      for(int j=1;j<=n;j++)
      {
        if ((map[i][j]>dmap[i])&&(map[i][j]<maxn)) dmap[i]=map[i][j];
        if(temp<dmap[i]) temp=dmap[i];
      }

    for(int p=1;p<=n;p++)
      for(int q=1;q<=p;q++)
        if ((map[p][q]==maxn)&&(p!=q))
        {
          map[p][q]=sqrt(pow(pos[p][0]-pos[q][0],2)+pow(pos[p][1]-pos[q][1],2));
          if(dis>(map[p][q]+dmap[p]+dmap[q])) dis=map[p][q]+dmap[p]+dmap[q];
          map[p][q]=maxn;
        }
    
    if(dis<temp) dis=temp;//包含关系
    fout.precision(6); //控制精度
    fout.setf(ios::fixed); //输出小数点
    fout<<dis<<endl;

    return 0;
}

后记

本文是百度空间的移植，附：全部USACO题目解答。