あと一歩で全完逃した。
http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_c
問題
連結無向グラフが与えられる。
距離が3となる頂点対があり、かつ両者を直接つなぐ辺がない場合、両者に辺を追加できる。
最大何本の辺を追加できるか。
解法
距離3の頂点対に辺を張るということは、距離を2ずつ縮めることが可能である。
よって、もともと距離が奇数である頂点間の距離を1にできる。
元々のグラフが奇数長の閉路を持つ場合、任意の頂点間を奇数距離で移動できるので、辺を追加して完全グラフにできる。
そうでない場合、つまり二部グラフの場合、二部に分けた両者の間で全頂点間に辺を張れる。
int N,M; vector<int> E[101010]; int C[101010]; int num[101010]; void dfs(int cur,int col) { if(C[cur]!=-1) { if(C[cur]!=col) { cout<<1LL*N*(N-1)/2-M<<endl; exit(0); } } else if(C[cur]==-1) { C[cur]=col; num[col]++; FORR(e,E[cur]) dfs(e,col^1); } } void solve() { int i,j,k,l,r,x,y; string s; MINUS(C); cin>>N>>M; FOR(i,M) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } dfs(0,0); cout<<1LL*num[0]*num[1]-M<<endl; }
まとめ
こちらはあまり苦労しなかった。