PKU 1632 Vase collection
http://poj.org/problem?id=1632
36種類の形と36種類の模様が存在するツボがある。
今、このうちのいくつかの形と模様の組み合わせられたツボがある。
ここでk種類の形とk種類の模様を指定した時、k*kの形と模様の組み合わせのツボがすべての存在するような最大のkを求めろというような問題。
深さ優先探索でTLEしたので、幅優先しました。
ll g[36]; ll r[36]; int ans; bool can(ll st,int sz){ ll ko=(1LL<<36)-1; rep(i,36){ if(st&(1LL<<i))ko&=g[i]; } int ok=0; rep(i,36){ if((ko&(1LL<<i)) && (r[i]&st)==st)++ok; } return ok>=sz; } void solve(){ int m; cin>>m; memset(g,0,sizeof(g)); memset(r,0,sizeof(r)); rep(i,m){ ll a,b; cin>>a>>b; --a,--b; g[a]|=1LL<<b; r[b]|=1LL<<a; } ans=0; queue<pair<ll,ll> > q; q.push(mp(0,0)); set<ll> app; while(!q.empty()){ ll sz=q.front().F; ll st=q.front().S; q.pop(); if(app.count(st))continue; ans=sz; app.insert(st); rep(i,36){ if(st&(1LL<<i))continue; if(can(st|1LL<<i,sz+1))q.push(mp(sz+1,st|1LL<<i)); } } cout<<ans<<endl; } main(){ int T; cin>>T; while(T--)solve(); }