kmjp's blog

競技プログラミング参加記です

VK Cup 2015 Round 3 : E. Playing on Graph

本番は時間切れで問題も読んでない。
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が小さいから愚直に総当たりで良かったのね。