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行)