UOA1032: Course Planning for Lazy Students
ACM-ICPC Japan Domestic Warm Up IのD問題。BFSで解けるという噂を聞いたのでやってみました。
ノーデバッグで一発Accepted。なんと。
実行時間がすごいことになりました。高速化したくなった問題はいくらでもありますが、むしろ高速化したくない問題は初めてです。
#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <string> #include <cassert> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; #define REP(i,e) for(int i=0;i<(int)(e);i++) #define FOR(i,b,e) for(int i=(b);i<(int)(e);i++) #define ALL(c) (c).begin(), (c).end() #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i) const int N=20; int req[N]; int deg[N]; bool done[1<<N]; struct state{ int s,c; }; int bitcount(int n){ return n ? (n&1)+bitcount(n>>1) : 0; } int BFS(int n,int r){ queue<state> qu; for(qu.push((state){0,0});qu.size();qu.pop()){ state s=qu.front(); if(done[s.s]) continue; done[s.s]=true; if(s.c>=r) return bitcount(s.s); REP(i,n) if(!(s.s&(1<<i)) && (req[i]&s.s)==req[i]) qu.push((state){s.s|(1<<i),s.c+deg[i]}); } assert(false); } main(){ int n,r; while(cin >> n >> r && n|r){ REP(i,n){ int a,b; req[i]=0; cin >> deg[i] >> a; REP(j,a) cin >> b, req[i]=req[i]|(1<<b); } REP(i,1<<n) done[i]=false; cout << BFS(n,r) << endl; } }