链接：https://ac.nowcoder.com/acm/contest/64221/A
来源：牛客网
来源：牛客网
题目描述
在Stellaris的宇宙中，有着许多强大的帝国，帝国之间经常发生争斗，现在在宇宙中一共有 ?w 个帝国。
有 ?n 个星系，每个星系都被一个帝国所占领，有条通道，每条通道可以让两个星系之间连通，但是通道仅有在两个星系都属于同一个帝国的时候，才可以发挥资源运输的作用。
由于丁真帝国和王源帝国的种族思想不同，丁真帝国想要发动星际战争攻打王源帝国，急需矿产资源，建造星际舰队，但是丁真帝国所占领的星系并没有互相连接，导致星系之间的矿产资源不能进行运输，所以只能在一块连通的地区内进行舰队的建造。不过丁真帝国已经可以建筑星门这种巨构，一个星门可以通往其他任意另一个星门，但是由于资源问题，丁真帝国最多只能建造 ?k 个星门。
作为丁真帝国的总指挥的你现在需要计算怎么样建造星门才能使流通的矿产资源最大化（默认 1 属于丁真帝国）？
你说得对 但是《王源剩太多》是由丁真珍珠自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「理塘」的幻想世界，在这里被神选中的人将被授予「电子烟」，引导尼古丁之力。你将扮演一位名为「芙蓉王」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的动物朋友们，和它们一起击败强敌，找回不存在的亲人的同时，逐步发掘「理塘」的真相。
输入描述:
第一行输入四个整数 ?n，?m，?k，?w，?n表示星系的数量，?m 表示通道的数量，?k 表示最多可以建造的星门的数量，?w表示帝国的总数量1≤?,?≤1061≤n,w≤106，0≤?,?≤1060≤k,m≤106。
第二行输入一行正整数 ??ai，表示第 ?i个星系的矿产资源总数，0≤??≤1060≤ai≤106。
第三行输入一行正整数 ??bi，表示第 ?i个星系的属于哪个帝国，1≤??≤?1≤bi≤n，默认 1 属于丁真帝国
接下来 m 行每行两个数 ?,?x,y，表示星系 ?x与星系 ?y 之间有一条通道连接，1≤?,?≤?1≤x,y≤n，数据保证不会有重边和自环 。
输出描述:
输出一个整数，表示丁真帝国最大的流通矿物资源数量。
备注:
样例中，4和5是相互连接的，用星门将1,4,5,7连通，最大的矿产流通资源量为19本题容易看出核心思路就是贪心，就是要寻找丁真的星系里面连通区域大的。那么在这里就要考虑如何去计算丁真的星系连通区域的资源总和。
在记录了各个星系与哪些星系之间有通道（vc）之后，通过BFS广度优选遍历，先将直接相邻的星系遍历一遍计算这些星系的资源总数，然后通过v2来记录这些相邻的星系，以便于接着深入每一个相邻星系去遍历。在过程中也要注意不能出现重复遍历的情况，那么可以搞一个c来记录当前星系是否已经被遍历过了。将连通区域的资源总和全部计算完成之后按照从大到小的顺序排序贪心的去从大到小选择即可。（要注意资源总和要使用long long）。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e6+10;
int a[maxn];
int b[maxn];
int c[maxn];
vector<ll> v1;
vector<int> v2;
vector<int> vc[maxn];
int main() {
int n, m, k, w;
int x, y, j;
scanf("%d%d%d%d", &n, &m, &k, &w);
for (int i=1;i<=n;i++) {
scanf("%d", &a[i]);
}
for (int i=1;i<=n;i++) {
scanf("%d", &b[i]);
}
for (int i=1;i<=m;i++) {
scanf("%d %d", &x, &y);
vc[x].push_back(y); vc[y].push_back(x);
}
for (int i=1;i<=n;i++) {
if (c[i]==0&&b[i]==1) {
v2.clear(); v2.push_back(i); j=0;
c[i] = 1;
ll t = a[i];
while (j<v2.size()) {
int x = v2[j];
j++;
//遍历直接相邻的星系
for (int ij=0;ij<vc[x].size();ij++) {
//如果没有被遍历到并且是丁真的星系
if (c[vc[x][ij]]==0&&b[vc[x][ij]]==1) {
c[vc[x][ij]] = 1;
t += a[vc[x][ij]];
v2.push_back(vc[x][ij]);
}
}
}
v1.push_back(t);
}
}
sort(v1.begin(), v1.end(), greater());
int i = 0;
ll ans = 0;
while (i<v1.size()&&k>0) {
ans += v1[i];
i++;k--;
}
printf("%lld", ans);
return 0;
}
京公网安备 11010502036488号