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;
  }
}