E - Independence

E - Independence

解法
辺で繋がっていない都市は、別のグループに属さないといけない
よって補グラフが二部グラフでなければ答えは-1

二つの集合サイズを均等に分けると答えが最小になる
これは、ナップザックにより解ける
グラフは複数の二部グラフに分けられるが、それらをabで塗り分ける際にaは何頂点あるか、bは何頂点あるかを求めておき
各色を自由に入れ替えればいい

>|c++|

template bool nibu(const graph &g) {
if (g.edges.size() == 0)return true;
UnionFind uf(g.n * 2);
for (auto &&e :g.edges)uf.unite(e.from, e.to + g.n), uf.unite(e.from + g.n, e.to);
rep(i, g.n)if (uf.same(i, i + g.n))return 0;
return 1;
}
//二部グラフを色分けした際の頂点数を返す
template vp nibug(graph &g) {
vp cg;
if (!nibu(g))ole();
int _n = g.size();
vb _was(_n);
queue

q;
rep(i, _n) {
if (_was[i])continue;
q.push(mp(i, 1));
_was[i] = 1;
int red = 0;
int coun = 0;
while (q.size()) {
int now = q.front().F;
int col = q.front().S;
red += col;
coun++;
q.pop();
forg(gi, g[now]) {
if (_was[t])continue;
q.push(mp(t, col ^ 1));
_was[t] = 1;
}
}
cg.push_back(mp(red, coun - red));
}
return cg;

}

undigraph<> g(2 * k5);
void solve() {
cin >> n >> m;
vvi (link, 1000, 1000);
g.resize(n);
rep(i, m) {
int f, t;
cin >> f >> t;
--f, --t;
link[f][t] = 1;
link[t][f] = 1;
}
rep(i, n)rep(j, i)if (link[i][j] == 0 && i != j)g.add(i, j);
if (!nibu(g)) {
fin(-1);
} else {
vp gr = nibug(g);
vvb (dp, 1000, 1000);
dp[0][0] = 1;
rep(i, sz(gr)) {
rep(j, 1000) {
if (dp[i][j] == 0)con;
dp[i + 1][j + gr[i].fi] = 1;
dp[i + 1][j + gr[i].se] = 1;
}
}
rep(i, 1000)if (dp[sz(gr)][i])chmin(mi, sig(i - 1) + sig(n - i - 1));
cout << mi << endl;
}
}