UVa 10985 - Rings'n'Ropes

UVa 10985 - Rings'n'Ropes
http://uva.onlinejudge.org/external/109/10985.html

問題概要

n個のリングと、m本のひもがある。
どのように今結ばれているかの情報が与えられる。
ただし、ひとつのリングのペアにたいしてはひもが一本。
自分自身を結ぶようなひもも存在しない。
ふたつのリングを持ち、伸ばした時、ピンとはるひもの長さの合計をもとめなさい。

解法

探索。
1　ワーシャルフロイドをかける。
2　伸ばすリングを片方きめる。
3　各リングについて、そのリングがもしピンとはるリングになりうる場合、
今決めてる片方に近い側でピンとある可能性があって、そのリングに繋がっているものの数を数える。
それは、今決めている片方とそのリングとの最短経路に使われるひもの数である。
4　ピンとはる可能性のあるリングを列挙する。そのリングについて3でもとめたものを合計する。
これらの操作をして、一番多いものが答え。

ソース

#include<iostream>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
using namespace std;
const int INF = 1000000000;
const int V = 120;
int main(){
  int T;
  cin >> T;
  rep(tc, T){
    int edge[V][V];
    cout << "Case #" << tc+1 << ": ";
    int v, e;
    cin >> v  >> e;
    rep(i, v){
      rep(j, v){
        edge[i][j] = INF;
      }
      edge[i][i] = 0;
    }
    rep(i, e){
      int from, to;
      cin >> from >> to;
      edge[from][to] = edge[to][from] = 1;
    }
    rep(k, v){
      rep(i, v){
        if(edge[i][k] == INF)continue;
        rep(j, v){
          if(edge[k][j]==INF)continue;
          edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
        }
      }
    }
    int ans = 0;
    rep(from, v){
      int cnt[V];
      rep(i, v)cnt[i] = 0;
      rep(i, v){
        rep(j, v){
          if(edge[j][i] == 1 && edge[from][i] == edge[from][j] + 1){
            cnt[i]++;
          }
        }
      }
      rep(to, v){
        int res = 0;
        rep(i, v){
          if(edge[from][i] + edge[i][to] == edge[from][to]){
            res+= cnt[i];
          }
        }
        ans = max(res, ans);
      }
    }
    cout << ans << endl;
  }
  return 0;
}