1032 Course Planning for Lazy Students
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1032&lang=jp
概要
最低限の単位数を確保する最小の講義数を求める問題。
ある講義に対して、あらかじめとっておかないといけない講義がある場合がある。
ほうしん
うまいやり方が思いつかなかったので、BFSした。
最初DFSしてたのだけれど、どうしてもTLEしてしまうようでBFSに変更 & bitを使って高速化した。
1msとかの人もいるので、もっとうまいやり方があるのだと思う。
ソース
#include<iostream> #include<vector> #include<cstring> #include<queue> using namespace std; #define REP(i,a,b) for(i=a; i<b; ++i) #define rep(i,n) REP(i,0,n) vector<int> cv,pv; int n,U; bool visited[1<<20]; struct state { int used,cost; state(int used,int cost) : used(used), cost(cost) {;} }; int pop(int x) { int n = 0; while(x != 0) { n++; x &= (x-1); } return n; } int bfs() { queue<state> Q; Q.push(state(0,0)); int i; while(!Q.empty()) { state ns = Q.front(); Q.pop(); if(visited[ns.used]) continue; if(ns.cost >= U) { return pop(ns.used); } visited[ns.used] = 1; for(i=0; i<n; ++i) { if(!(ns.used&(1<<i)) && (ns.used & pv[i])==pv[i]) { Q.push( state(ns.used|(1<<i), ns.cost+cv[i]) ); } } } return 0; } int main() { int i,j,k,c,r,tmp; while(cin>>n>>U, n|U) { cv.clear(); pv.clear(); pv.resize(n); rep(i, 1<<n) visited[i] = false; rep(i,n) { cin>>c>>k; cv.push_back(c); tmp = 0; rep(j,k) { cin>>r; tmp |= (1<<r); } pv[i] = tmp; } cout<<bfs()<<endl; } }