首页 > 试题广场 >

小欧皇

[编程题]小欧皇
  • 热度指数：2228 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小欧正在扮演一个中世纪的皇帝。地图上有 n 个城市，其中有 m 条道路，每条道路连接了两个城市。
\hspace{15pt}小欧占领了其中一些城市。如果两个城市可以通过若干条道路互相到达，且这些道路经过的城市都是小欧占领的，那么这两个城市之间就可以通过经商获得收益 1。请注意，每两个城市之间的收益只会被计算一次。
\hspace{15pt}现在，小欧准备占领一个未被占领的城市，使得总收益最大化。你能帮帮她吗？

输入描述:
\hspace{15pt}第一行输入两个正整数 n,m \left( 1 \leqq n,m \leqq 10^5\right)，代表城市数量和道路数量。
\hspace{15pt}第二行输入一个长度为 n 的 01 串。第 i 个字符为 '0' 代表小欧未占领该城市，'1' 代表小欧已经占领了该城市。
\hspace{15pt}接下来的 m 行，每行输入两个正整数 u,v \left(1 \leqq u,v \leqq n, u \neq v\right)，代表城市 u 和城市 v 有一条道路连接。


输出描述:
\hspace{15pt}输出一行两个空格隔开的整数，第一个整数代表占领的城市编号，第二个整数代表占领后的收益。
\hspace{15pt}请保证收益的最大化。如果有多种方案收益最大，小欧会优先占领编号最小的城市。
示例1

输入

5 5
01010
1 2
1 3
1 4
4 5
1 5

输出

1 3

说明

占领 1 号城市后，总收益为 3。
1 号城市和 2 号城市经商，1 号城市和 4 号城市经商，2 号城市和 4 号城市经商。

算法知识视频讲解
开通博客
头像 写烂代码的烂程序员
发表于 2024-10-28 22:49:55
并查集 使用并查集维护维护当前状态下联通块的大小。 建图的时候只考虑会有影响的边。 每个联通块的收益值是 首先计算当前状态下的收益值 对于每个可能占领的城市，我们计算收益的增加值 遍历每个可能的连通块 初始的时候 我们新的城市算一个联通块大小为1，假设遍历的第一个连通块大小为 则此时增量为 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 阿里嘎多懒羊羊桑_
发表于 2024-11-29 14:11:18
题意小欧正在扮演一个中世纪的皇帝。地图上有n个城市，其中有m条道路，每条道路连接了两个城市。小欧占领了其中一些城市。如果两个城市可以通过若干条道路互相到达，且这些道路经过的城市都是小欧占领的，那么这两个城市之间就可以通过经商获得收益1。请注意，每两个城市之间的收益只会被计算一次。现在，小欧准备占领一 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 MiaoYu404
发表于 2025-11-08 23:10:09
思路 如果两个被占领的城市之间存在一条道路，那么就可以用并查集合并。对于两个集合的合并： 集合 中所有元素与集合 中所有元素建立一条连边，总共 条。 先统计所有占领的联通块内部能获得多少收益，然后遍历所有未占领的城市，尝试将其与所有相邻的占领连通块合并，计算出收益增量，取其中最高的一个。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Mag1c0nch
发表于 2024-11-28 21:20:41
每个连通块对答案的贡献是固定的，如果连通块内有 n 个点，那么答案就是 n*(n-1)/2 ，所以我们可以用并查集维护出所有的连通块，然后维护出初始的答案，然后枚举剩下的所有为 0 的点变成 1 以后的情况，他会连接所有的相邻的 1 的连通块 #include <bits/stdc++.h&g 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Kato_Shoko
发表于 2024-11-27 19:08:45
#include <iostream> #include <queue> #include <map> #include <set> #include <cmath> #include <cstring> #include &l 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 czcczz
发表于 2025-11-10 21:17:58
#include<bits/stdc++.h> using namespace std; #define int long long const int N=100005; int n,m; int a[N],siz[N]; bool vis[N]; vector<int> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 365cent
发表于 2025-11-08 20:41:39
#include <stdio.h> #include <stdbool.h> int *to, *nxt, *head; // global adjacency arrays int idx; static inline int find(int x, int p[] 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 appley
发表于 2025-11-11 10:57:42
import java.util.*; class Edge { int to; int nxt; Edge(int t,int n) { to = t; nxt = n; } } public class Main { st 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-02 14:46:26
题目链接 小欧皇 题目描述 在一个由 个城市和 条道路构成的图中，一部分城市已被占领。如果两个城市可以通过一条完全由已占领城市构成的路径相连，则它们属于同一个“商业区”。一个大小为 的商业区，内部可以产生 对商业关系，每对关系产生 点收益。 现在需要从未占领的城市中选择一个进行占领，目标是 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
7条回答 1443浏览

热门推荐

相关试题

小欧皇

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号