63 lines
1.3 KiB
TypeScript
63 lines
1.3 KiB
TypeScript
export {};
|
|
const input = require("fs").readFileSync(0).toString().trim().split("\n");
|
|
|
|
const [N, M, K]: number[] = input[0].split(" ").map(Number);
|
|
let candy: number[] = [0].concat(input[1].split(" ").map(Number));
|
|
|
|
let rank: number[] = new Array(N+1).fill(0);
|
|
let parent: number[] = Array.from({length : N+1}, (_, i) => i);
|
|
|
|
const find = (x: number): number => {
|
|
if(x !== parent[x]) return parent[x] = find(parent[x]);
|
|
return parent[x];
|
|
};
|
|
|
|
const union = (x: number, y: number) => {
|
|
x = find(x);
|
|
y = find(y);
|
|
|
|
if(x === y) return;
|
|
|
|
if(rank[x] < rank[y]) {
|
|
const temp = x;
|
|
x = y;
|
|
y = temp;
|
|
}
|
|
|
|
parent[y] = x;
|
|
|
|
if(rank[x] === rank[y]) rank[x]++;
|
|
}
|
|
|
|
for(let i=0; i<M; i++) {
|
|
const [a, b]: number[] = input[i+2].split(" ").map(Number);
|
|
union(a, b);
|
|
}
|
|
|
|
let count: {[key: number] : number} = {};
|
|
for(let i=1; i<=N; i++) {
|
|
const root: number = find(i);
|
|
count[root] = (count[root] ?? 0) + 1;
|
|
if(root === i) continue;
|
|
candy[root] += candy[i];
|
|
}
|
|
|
|
let pair: number[][] = [];
|
|
for(let key in count) {
|
|
pair.push([count[key], candy[Number(key)]]);
|
|
}
|
|
|
|
let dp: number[] = new Array(K+1).fill(0);
|
|
|
|
for(let [w, v] of pair) {
|
|
for(let k=K; k>=w; k--) {
|
|
dp[k] = Math.max(dp[k], dp[k-w] + v);
|
|
}
|
|
}
|
|
|
|
let res: number = 0;
|
|
for(let k=1; k<K; k++) {
|
|
res = Math.max(res, dp[k]);
|
|
}
|
|
|
|
console.log(res); |