なかなか面白かった。
http://codeforces.com/contest/557/problem/D
問題
N頂点M辺の無向グラフが与えられる。
ここにT辺を追加して奇数長の閉路を作りたい。
最小のTと、追加するT辺の組み合わせの数を求めよ。
解法
グラフが二部グラフを成す場合、奇数長の閉路ができない。
まずグラフが二部になるか判定しよう。
これはDFSで点を2色に塗り分けてもいいし、頂点を2*N個用意してUnion-Findを用いる方法もある。
最小3本辺を追加すれば長さ3の閉路ができるので、加える辺の長さは0~3の何れかである。
- 追加が0本のケース:
- 二部グラフにならない連結成分があるとき、すでに奇数長の閉路があることになるので追加不要。
- 追加が1本のケース:
- 追加が3本のケース:
- 1本も辺がない場合、3点選んで3本辺を追加すればよいので通り。
- 追加が2本のケース:
- 各頂点の次数が0~1の場合、各辺を跨ぐ2点と、その他の点を1個選べば三角形が作れる。
- よってM*(N-2)通りの閉路が作れる。
template<int um> class UF { public: vector<int> par,rank,cnt; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<201010> uf; ll N,M; vector<int> E[101010]; int num[202020][2]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; x--,y--; E[x].push_back(y); E[y].push_back(x); uf(x,y+N); uf(x+N,y); } FOR(x,N) if(uf[x]==uf[x+N]) return _P("0 1\n"); if(M==0) return _P("3 %I64d\n",N*(N-1)*(N-2)/6); FOR(i,2*N) { if((i<N)^(uf[i]<N)) num[uf[i]][0]++; else num[uf[i]][1]++; } ll ret=0; FOR(i,2*N) if(num[i][0]+num[i][1]>=3) ret += (1LL*num[i][0]*(num[i][0]-1)+1LL*num[i][1]*(num[i][1]-1))/2; if(ret) return _P("1 %I64d\n",ret/2); _P("2 %I64d\n",M*(N-2)); }
まとめ
ちょっと頭をひねる問題でした。