ARC099 E - Independence

AtCoder Regular Contest
問題

n個の街とm本の無向辺があり、これらの街を2つの州に分けたい
ただし同じ州内のどの2つの都市も直接道で結ばれているように分けないといけない
そういうふうに分けたときの、"両端の都市が同じ州内に属しているような道"の本数の最小値を求める

解法

条件は
「グラフからできるだけ多くの辺を取り除いて、グラフ全体がちょうど2つのクリークの合併になるようにする」
と言い換えられ、これは更に
「補グラフにできるだけ多くの辺を加えて、グラフ全体が完全二部グラフになるようにする」
と言い換えられる

完全二部グラフを作るためには初期状態の補グラフが二部グラフになっていないと無理
二部グラフになっている場合は、各連結成分の片方の集合Sともう片方Tのどっちをどっちの州に入れるかは自由に決められる
これをうまく調整して高州に所属する街数xと橋州の街数yについて x(x-1)/2 + y(y-1)/2を最小化すればいい

一応xとyはなるべくn/2に近い ∴ なるべく均等に分けたほうが良いことはすぐわかる
(今回はそこは重要じゃないしコードでも使ってないけど)

実装

補グラフで二部グラフ判定(col())
→二部グラフと確認できたら連結成分ごとにSとTに分け、サイズをメモ(rec())
→部分和dpで、あり得る州の分け方を全通り列挙して最小値を探す

あるグラフのクリークはその補グラフの独立集合に対応する ってのが典型らしい
今回初めて見た

int n, m, a, b, d[777][777], c[777], s[777], t[777], k, res = inf;
bool u[777], dp[777][777];

bool col(int v, int x) {
	c[v] = x;
	rep(i,n) {
		if (i==v || d[v][i]) continue;
		if (c[i]==x) return 0;
		if (!c[i] && !col(i,-x)) return 0;
	}
	return 1;
}

void rec(int v) {
	u[v] = 1;
	(c[v]==1 ? s : t)[k]++;
	rep(i,n) if (!d[v][i] && !u[i]) rec(i);
}

int main() {
	cin >> n >> m;
	rep(i,m) {
		cin >> a >> b;
		a--, b--;
		d[a][b] = d[b][a] = 1;
	}
	rep(i,n) if (!c[i] && !col(i,1)) return cout << -1, 0;
	rep(i,n) if (!u[i]) rec(i), k++;
	dp[0][0] = 1;
	rep(i,k) rep(j,n) if (dp[i][j]) dp[i+1][j+s[i]] = dp[i+1][j+t[i]] = 1;
	rep(i,n) if (dp[k][i]) chmin(res, i*(i-1)/2 + (n-i)*(n-i-1)/2);
	cout << res;
}