本番は時間切れで問題も読んでない。
http://codeforces.com/contest/542/problem/E
問題
N頂点M辺のグラフが与えられる。
このグラフに対して縮約を繰り返す。
縮約とは、2つの(間に辺をもたない)点を選び、それらを1つにまとめることである。
元の2頂点に隣接する点は、縮約後ではまとめた辺に隣接する。
適切な縮約を繰り返し、このグラフが1本のpath(分岐も閉路もないグラフ)となるようにしたい。
得られる最長のpath長を求めよ。
解法
各連結成分について最長のpathを求め、それらを縮約で連結すればよい。
よって各連結成分内の最長pathの求め方を考えよう。
まずpathが生成できない場合を考える。
path内に奇数長の閉路がある、すなわち2部グラフに出来ない形になっていると、閉路をつぶしてpathに出来ない。
よって最初に二部グラフかどうかの判定を行う。
あとは最長pathの計算だが、Nがさほど大きくないので各頂点を始点とし、最遠点をBFSで求めればよい。
int N,M; vector<int> E[1010]; int vis[1010], gr[1010]; int len[1010],d[1010]; vector<int> cand; void dfs(int cur,int col,int g) { gr[cur]=g; if(vis[cur]!=-1) { if(vis[cur]!=col) { _P("-1\n"); exit(0); } } else { vis[cur]=col; FORR(r,E[cur]) dfs(r,col^1,g); } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } MINUS(vis); FOR(i,N) if(vis[i]==-1) cand.push_back(i), dfs(i,0,i); FOR(i,N) { FOR(x,N) d[x]=1010; d[i]=0; queue<int> Q; Q.push(i); while(Q.size()) { x=Q.front(); Q.pop(); FORR(r,E[x]) if(d[r]>d[x]+1) d[r]=d[x]+1, len[gr[i]]=max(len[gr[i]],d[r]),Q.push(r); } } cout<<accumulate(len,len+N,0)<<endl; }
まとめ
閉路もあるのに最遠点対どうやって求めようと思ったけど、Nが小さいから愚直に総当たりで良かったのね。