kmjp's blog

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

CODE FESTIVAL 2017 Qual B : C - 3 Steps

あと一歩で全完逃した。
http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_c

問題

連結無向グラフが与えられる。
距離が3となる頂点対があり、かつ両者を直接つなぐ辺がない場合、両者に辺を追加できる。
最大何本の辺を追加できるか。

解法

距離3の頂点対に辺を張るということは、距離を2ずつ縮めることが可能である。
よって、もともと距離が奇数である頂点間の距離を1にできる。

元々のグラフが奇数長の閉路を持つ場合、任意の頂点間を奇数距離で移動できるので、辺を追加して完全グラフにできる。
そうでない場合、つまり二部グラフの場合、二部に分けた両者の間で全頂点間に辺を張れる。

int N,M;
vector<int> E[101010];
int C[101010];
int num[101010];

void dfs(int cur,int col) {
	if(C[cur]!=-1) {
		if(C[cur]!=col) {
			cout<<1LL*N*(N-1)/2-M<<endl;
			exit(0);
		}
	}
	else if(C[cur]==-1) {
		C[cur]=col;
		num[col]++;
		FORR(e,E[cur]) dfs(e,col^1);
		
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(C);
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,0);
	
	cout<<1LL*num[0]*num[1]-M<<endl;
	
}

まとめ

こちらはあまり苦労しなかった。