USACO2.43Cow Tours（floyd+dfs)

dfs用来求这个节点属于哪一块用floyd求出各点间的最短距离再求出每个节点可达到的最远距离MAX[i]以及这两个块中的最长距离a,b. 枚举当两个节点不在一块中 dis = max{(dis[i][j]+MAX[i]+MAX[j] ),a,b),在求出dis中最小的。

View Code

 1 /*
 2      ID: shangca2
 3      LANG: C++
 4      TASK: cowtour
 5  */
 6 #include <iostream>
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<algorithm>
10 #include<stdlib.h>
11 #include<cmath>
12 using namespace std;
13 #define INF 0x3f3f3f
14 struct node
15 {
16     int x,y;
17 }no[200];
18 double w[200][200],m[200],a[5];
19 int n,vis[200];
20 void dfs(int x,int d)
21 {
22     int i;
23     for(i = 1; i <= n ; i++)
24         if(!vis[i]&&w[x][i]!=INF)
25         {
26             vis[i] = d;
27             dfs(i,d);
28         }
29 }
30 int main()
31 {
32     freopen("cowtour.in","r",stdin);
33     freopen("cowtour.out","w",stdout);
34     int i,j,k;
35     char c;
36     cin>>n;
37     for(i = 1; i <= n ; i++)
38     cin>>no[i].x>>no[i].y;
39     for(i = 1; i <= n ; i++)
40     {
41         for(j = 1; j <= n ; j++)
42         {
43             cin>>c;
44             if(c=='1')
45             w[i][j] = 1.0*sqrt((no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y));
46             else
47             w[i][j] = INF;
48         }
49     }
50     int g = 1;
51     for(i = 1; i <= n ; i++)
52         if(!vis[i])
53         {
54             vis[i] = g;
55             dfs(i,g++);
56         }
57     for(i = 1; i <= n ; i++)
58     w[i][i] = 0;
59     for(i = 1; i <= n ; i++)
60         for(j = 1; j <= n ; j++)
61             for(k = 1; k <= n ; k++)
62             {
63                 if(w[j][k]>w[j][i]+w[i][k])
64                 w[j][k]=w[j][i]+w[i][k];
65             }
66     for(i = 1; i <= n ; i++)
67         for(j = 1; j <= n ;j++)
68         {
69             if(w[i][j]<INF)
70             a[vis[i]] = max(a[vis[i]],w[i][j]);
71         }
72     for(i = 1; i <= n ; i++)
73     {
74         m[i] = 0;
75         for(j = 1; j <= n ; j++)
76         if(w[i][j]<INF)
77         m[i] = max(m[i],w[i][j]);
78     }
79     double mi=INF,mm = INF;
80 
81     for(i = 1; i <= n ; i++)
82     {
83         for(j = 1; j <= n ; j++)
84         {
85             if(vis[i]!=vis[j])
86             {
87                 mi = m[i]+m[j]+1.0*sqrt((no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y));
88                 mi = max(mi,a[1]);
89                 mi = max(mi,a[2]);
90             }
91             if(mi<mm)
92             mm = mi;
93         }
94     }
95     printf("%.6lf\n",mm);
96     return 0;
97 }