第8回日本情報オリンピック 春合宿 4日目 問題1 「冊子の配布」 (Distribution)

貪欲法
計算量がO(NM)でNM = 10^7だから「計算量ちょっとやばいかなー」と思ってできるだけ高速に実行できるように頑張ったけど実際そんなことやる必要なかった問題。

#include <bits/stdc++.h>

using namespace std;

int n,m,co,ans,yaruki[10003],ruisekiyaruki[10003],oya[10003],kouho[10009];
vector<int> ko[10003];
void ddfs(int nau,int hiku){
	ruisekiyaruki[nau] -= hiku;
	for(int i = 0;i < ko[nau].size();i++){
		ddfs(ko[nau][i],hiku);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int s,a;
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&s,&a);
		ko[s].push_back(i);
		yaruki[i] = a;
		oya[i] = s;
	}
	for(int i = 1;i <= n;i++){
		ruisekiyaruki[i] += yaruki[i];
		for(int j = 0;j < ko[i].size();j++){
			int k = ko[i][j];
			ruisekiyaruki[k] += ruisekiyaruki[i];
		}
		if(ko[i].empty()) kouho[co++] = i;
	}
	while(m--){
		int c = -1,ban;
		for(int i = 0;i < co;i++){
			if(c < ruisekiyaruki[kouho[i]]){
				c = ruisekiyaruki[kouho[i]];
				ban = i;
			}
		}
		if(c == -1)break;
		ans += c;
		ruisekiyaruki[kouho[ban]] = -1;
		int nau = oya[kouho[ban]];
		while(nau != 0){
			if(ruisekiyaruki[nau] == -1)break;
			for(int j = 0;j < ko[nau].size();j++){
				if(ruisekiyaruki[ko[nau][j]] == -1)continue;
				ddfs(ko[nau][j],ruisekiyaruki[nau]);
			}
			ruisekiyaruki[nau] = -1;
			nau = oya[nau];
		}
	}
	printf("%d\n",ans);
	return 0;
}