これは750ptでもいい気がする。
http://codeforces.com/contest/741/problem/B
問題
N個のHos(架空の動物?)がおり、それぞれの重さはW[i]、価値はB[i]である。
また、友人関係にある2者の対が複数与えられる。
友人関係による連結成分を友人グループと呼ぶ。
各グループより以下のいずれかの友人の選び方をしたい。
- 1人も選ばない
- 1人だけ選ぶ
- 全員選ぶ
上記条件のもとN個のHosのうち、総重量がWを超えない範囲で数個選択するとき、価値の総和の最大値を求めよ。
解法
Union-Findで友人グループに分類した後、各グループから最大1人もしくは全員選ぶナップサック問題のDPを解くだけ。
template<int um> class UF { public: vector<int> par,rank; UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<500000> uf; int N,M,WW; int W[1010]; int B[1010]; int X[101010],Y[101010]; vector<int> E[1010]; int from[1010]; int to[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>WW; FOR(i,N) cin>>W[i]; FOR(i,N) cin>>B[i]; FOR(i,M) { cin>>X[i]>>Y[i]; uf(X[i]-1,Y[i]-1); } FOR(i,N) E[uf[i]].push_back(i); FOR(i,N) if(E[i].size()) { int tw=0; int tb=0; FOR(j,1001) to[j]=from[j]; FORR(r,E[i]) { tw+=W[r],tb+=B[r]; // one for(x=W[r];x<=WW;x++) to[x]=max(to[x],from[x-W[r]]+B[r]); } for(x=tw;x<=WW;x++) to[x]=max(to[x],from[x-tw]+tb); swap(from,to); } cout<<*max_element(from,from+WW+1)<<endl; }
まとめ
なんでこれが1000ptのBなんだろう。