ちょっと戸惑った。
https://yukicoder.me/problems/no/2236
問題
N頂点M辺のグラフがある。
各点は白黒のいずれかで塗られている。
辺を1つ選び、両端の頂点の色を白黒反転させることができるとき、全頂点を白色にできるか判定せよ。
できるなら最小選択回数を示せ。
解法
Mが小さいので、半分全列挙で解く。
先頭floor(M/2)通りの辺の選択法を総当たりし、その結果の各頂点の色と、対応する操作回数の最小値のmapを持とう。
あとは後半ceil(M/2)通りの辺の選択法を総当たりし、先頭の辺の総当たり結果と合わせて全点白色にできるケースの最小操作回数を求める。
int N,M; int A[40],B[40]; ll BM; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>A[i]>>B[i]; A[i]--,B[i]--; } FOR(i,N) { cin>>x; BM|=((ll)x)<<i; } int mask; int ret=100; map<ll,int> memo; int L=M/2,R=M-L; FOR(mask,1<<L) { ll CM=BM; int step=0; FOR(i,L) if(mask&(1<<i)) { CM^=1LL<<A[i]; CM^=1LL<<B[i]; step++; } if(memo.count(CM)==0) memo[CM]=100; chmin(memo[CM],step); } FOR(mask,1<<R) { ll CM=0; int step=0; FOR(i,R) if(mask&(1<<i)) { CM^=1LL<<A[L+i]; CM^=1LL<<B[L+i]; step++; } if(memo.count(CM)) ret=min(ret,memo[CM]+step); } if(ret==100) ret=-1; cout<<ret<<endl; }
まとめ
半分全列挙、地味に実装苦手なんだよな。
もっとサラッと書けないかな。