UTPC 2013 : C - 直径

Codeforcesに出そうな問題。
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_03

問題

それぞれN[i]点・M[i]辺の2つのグラフが与えられる。
2つのグラフで点を1個ずつ選択し、その間に辺を張りたい。

全ての辺の距離が1の時、連結後のグラフの直径の最小値と最大値を答えよ。

解法

まず、両グラフそれぞれ各点を始点としたとき、他の全ての到達できる距離を求め、その最小値と最大値を求める。
これはO(NM)かかるがN<=10^3、M<=10^4なので何とか間に合う。

次に、連結後のグラフの最小値は以下のうちの最大値である。
前者は連結後のグラフの直径が最小になるよう、距離が最小となる点同士を連結した場合である。
後者は元の個々のグラフの直径がもともと大きい場合である。

• 元の個々のグラフにおける到達距離の最小値の和+1
• 元の個々のグラフにおける先ほど求めた最大値

連結後のグラフの直径の最大値は、元のグラフの全点到達距離の最大値を足して1加えたものである。

int N,M;
vector<int> E[1001];
int dist[1000];
int ma[2],mi[2];
int tmi,tma;

void solve() {
	int i,j,k,x,y,l;
	FOR(i,2) {
		cin>>N>>M;
		FOR(x,N) E[x].clear();
		FOR(x,M) {
			cin>>j>>k;
			E[j].push_back(k);
			E[k].push_back(j);
		}
		mi[i]=999999;
		ma[i]=0;
		FOR(x,N) {
			FOR(y,N) dist[y]=999999;
			dist[x]=0;
			tma=0;
			
			queue<int> Q;
			Q.push(x);
			while(!Q.empty()) {
				int cur=Q.front();
				Q.pop();
				FOR(j,E[cur].size()) {
					int tar=E[cur][j];
					if(dist[tar]<=dist[cur]+1) continue;
					dist[tar]=dist[cur]+1;
					tma=max(tma,dist[tar]);
					Q.push(tar);
				}
			}
			mi[i]=min(mi[i],tma);
			ma[i]=max(ma[i],tma);
		}
	}
	tma=max(ma[0],ma[1]);
	tma=max(tma,mi[0]+mi[1]+1);
	
	_P("%d %d\n",tma,ma[0]+ma[1]+1);
}

まとめ

文章だと分かりにくいな。
図だと明確なんだけど。