ARC099 E : Independence(700)

作成日:2018.10.03
最終更新日:2018.10.03

問題概要

問題本文

 $N$個の都市と都市$A_i$,$B_i$を結ぶ$M$本の道がある。 条件「同じ州に属すどの2つの都市も直接道で結ばれている」を満たすように都市を2つの州に分けたい。 これが可能であるかを判定せよ。 また可能である時、同じ州に属している都市の間にある道の本数の最小値を求めよ。
制約
$2 \leq N \leq 700$
$0 \leq M \leq N(N-1)/2$
$1 \leq A_i,B_i \leq N, \; A_i \neq B_i$
$i \neq j$ならば$\{A_i,B_i\} \neq \{A_j,B_j\}$

考え方

 都市と道をグラフとみなし、2つの州に分けることを2色に塗り分けることとする。 この時、条件は「同じ色の頂点間には辺がある」と言い換えられる。 これを満たすように頂点を色分けするには、間に辺がない2つの頂点は別の色で塗れば良い。 すなわち補グラフで考えると、辺で結ばれている頂点は別の色で塗るということになる。 これが可能であるのは補グラフが二部グラフである時に限るから、条件を満たす色分けが存在するかを判定することができる。
 色分けが可能である時、同じ色で塗られた頂点間にある辺の本数を最小化したい。 条件より同じ色の頂点だけを見ると完全グラフになっているので、頂点を$i$個と$(N-i)$個に色分けしたとすると求める辺の本数は$\frac{i(i-1)}{2} + \frac{(N-i)(N-i-1)}{2}$である。 後は$i$としてありうるものが列挙できれば、答えを求めることができる。
 補グラフが二部グラフである時、色の塗り分け方は連結成分ごとに$2$通りある。 すなわち連結成分$C$ごとに一方の色で塗られる頂点の個数は$x_C$,$y_C$($x_C \leq y_C$)のいずれかとなる。 $i \geq \sum x_C$であり、$i - \sum x_C$としてありうる値は$y_C - x_C$からいくつか選んで足し合わせたものになる。 これはDPで容易に求めることができる。
 計算量は$O(N^2)$であり、十分高速である。

ソースコード

マクロ等はこちら

const int MC = 704;
int N,M;
bool e[MC][MC];
int b[MC];
bool t[MC];

int main(){
	cin >> N >> M;
	repp(i,0,M){
		int A,B; cin >> A >> B; --A; --B;
		e[A][B] = e[B][A] = 1;
	}
	int s = 0;
	t[0] = 1;
	repp(i,0,N) if(!b[i]){
		int x = 0, y = 0;
		queue<int> Q; Q.push(i);
		b[i] = 1;
		while(!Q.empty()){
			int v = Q.front(); Q.pop();
			++(b[v]>0?x:y);
			repp(u,0,N) if(v != u && !e[v][u]){
				if(!b[u]){
					Q.push(u);
					b[u] = -b[v];
				} else if(b[v] == b[u]) return cout << -1 << endl , 0;
			}
		}
		if(x > y) swap(x,y);
		s += x;
		repm(k,N,y-x-1) t[k] |= t[k-y+x];
	}
	int ans = 1e9;
	repp(i,s,N+1) if(t[i-s]) ans = min(ans,i*(i-1)/2+(N-i)*(N-i-1)/2);
	cout << ans << endl;
	return 0;
}

解法まとめ

 補グラフが二部グラフでなければ答えは$-1$(不可能)である。(26行)
 そうでない時、補グラフの連結成分ごとにそれを二部グラフとしてみた時の2つのグループに含まれる頂点数$x_C$,$y_C$($x_C \leq y_C$)を求める。(16-30行)
 $y_C - x_C$からいくつか選んで足した値としてありうるものをDPで求める。(31行)
 答えはDPでありうると判定された値に$\sum x_C$を足した値$i$それぞれにおいて求めた$\frac{i(i-1)}{2} + \frac{(N-i)(N-i-1)}{2}$の最小値である。(33-35行)

ARC099の他の問題 C D F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告