この回は不参加だけど、これは自力で解けたかな。
https://arc099.contest.atcoder.jp/tasks/arc099_c
問題
N頂点M辺の無向グラフが与えられる。
このグラフを2つの完全グラフに分けることができるか。
できるとき、両グラフ内の辺の総数の最小値を求めよ。
解法
あり得る両完全グラフのサイズの組み合わせがわかれば、そのうち辺の総数が最小なものを求めればよい。
元のグラフの補グラフを考える。
元グラフが2つの完全グラフになるということは、同じ側の完全グラフに入る頂点間は、補グラフで辺があってはならない。
そこで、補グラフの各連結成分を考えよう。
条件より連結成分は二部グラフでなければならず、奇閉路がある場合解なしである。
二部グラフである場合、それぞれの頂点数をa,bとすると、どちらかを最終的な完全グラフの前者、後者に割り振ることになる。
これはDPの要領で両方を試せばよい。
int N,M; int C[700][700]; vector<int> E[707]; int vis[707]; int cnt[2]; int ok[707][707]; void dfs(int cur,int c) { if(vis[cur]!=-1) { if(vis[cur]==c) return; cout<<"-1"<<endl; exit(0); return; } cnt[c]++; vis[cur]=c; FORR(e,E[cur]) dfs(e,c^1); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; C[x-1][y-1]=C[y-1][x-1]=1; } FOR(x,N) { C[x][x]=1; FOR(y,N) if(C[x][y]==0) E[x].push_back(y); } ok[0][0]=1; int sum=0; MINUS(vis); FOR(i,N) if(vis[i]==-1) { cnt[0]=cnt[1]=0; dfs(i,0); FOR(x,sum+1) if(ok[x][sum-x]) { ok[x+cnt[0]][sum-x+cnt[1]]=1; ok[x+cnt[1]][sum-x+cnt[0]]=1; } sum+=cnt[0]+cnt[1]; } int mi=1<<30; FOR(x,N+1) if(ok[x][N-x]) mi=min(mi,x*(x-1)/2+(N-x)*(N-x-1)/2); cout<<mi<<endl; }
まとめ
これは気持ちよく解けて良かった。