UVA_10985

L和R的间距能拉多远是取决于L与R之间的最短路，因此，水平悬挂的绳一定是L和R之间最短路的一个部分。

而水平的Ring一定满足到L与R的距离和是L与R之间最短路的长度，因此我们可以先把所有水平的Ring找出来，符合要求的线一定是这些水平Ring之间的连线，但水平Ring之间的连线不一定符合要求（当两个Ring位于同一位置且恰好两者之间有一条连线，这条连线就不符合要求）。

因此，思路就是先用Floyd做最短路，然后枚举L、R并计算符合要求的连线的数目即可。

#include
     
       #include
      
        #define MAXD 150 #define INF 100000000 int f[MAXD][MAXD], M, N, res, ans[MAXD]; void init() {
   int i, j, a, b;     scanf("%d%d", &N, &M); for(i = 0; i < N; i ++) for(j = 0; j < N; j ++)         {
   if(i == j)                 f[i][j] = 0; else                 f[i][j] = INF;         } for(i = 0; i < M; i ++)     {
           scanf("%d%d", &a, &b);         f[a][b] = f[b][a] = 1;     } } void floyd() {
   int i, j, k; for(k = 0; k < N; k ++) for(i = 0; i < N; i ++) for(j = 0; j < N; j ++) if(f[i][k] + f[k][j] < f[i][j])                     f[i][j] = f[i][k] + f[k][j]; } void printresult() {
   int i, j, k, max = 0; for(i = 0; i < N; i ++) for(j = i + 1; j < N; j ++) if(f[i][j] != INF)             {
                   res = 0; for(k = 0; k < N; k ++) if(f[i][k] + f[k][j] == f[i][j])                         ans[res ++] = k; int p, q, temp = 0; for(p = 0; p < res; p ++) for(q = p + 1; q < res; q ++)                     {
   int a = ans[p]; int b = ans[q]; if(f[a][b] == 1 && f[i][a] != f[i][b])                             temp ++;                     } if(temp > max)                     max = temp;             }     printf("%d\n", max); } int main() {
   int t, tt;     scanf("%d", &t); for(tt = 0; tt < t; tt ++)     {
           init();         floyd();         printf("Case #%d: ", tt + 1);         printresult();     } return 0; }