PKU 1270 Following Orders
http://poj.org/problem?id=1270
ある集合内に含まれる要素とその中のいくつかのペアの大小が指定されるので、ソートされた状態としてありうる並べ方を全て出力しろというような問題。
枝刈りdfsしました。
int wall[30][30]; int suse[30]; int nuse[30]; char ctoi[128]; int sz=0; string cset; set<string> setans; char ans[30]; void dfs(int ne,int use){ if(ne==SZ(cset)){ ans[ne]=0; setans.insert(ans); return; } rep(i,SZ(cset)){ if(use&(1<<i))continue; if((suse[i]&use)!=suse[i])continue; if(nuse[i]&use)continue; ans[ne]=cset[i]; dfs(ne+1,use|1<<i); } } main(){ string in; while(getline(cin,in)){ memset(wall,0,sizeof(wall)); memset(ctoi,-1,sizeof(ctoi)); sz=0; cset.clear(); FOR(it,in){ if(isalpha(*it)){ cset+=*it; ctoi[*it]=sz++; } } getline(cin,in); stringstream ss(in); char a,b; while(ss>>a>>b)wall[ctoi[a]][ctoi[b]]=1; rep(i,sz)wall[i][i]=1; rep(k,sz)rep(i,sz)rep(j,sz)wall[i][j]|=wall[i][k]&wall[k][j]; setans.clear(); memset(suse,0,sizeof(suse)); memset(nuse,0,sizeof(nuse)); rep(i,sz)rep(j,sz){ if(i==j)continue; suse[i]|=wall[j][i]<<j; nuse[i]|=wall[i][j]<<j; } dfs(0,0); FOR(it,setans)cout<<*it<<endl; cout<<endl; } }