kmjp's blog

競技プログラミング参加記です

Codeforces #383 Div1 B. Arpa's weak amphitheater and Mehrdad's valuable Hoses

これは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なんだろう。