c++题目_分财产

发布于:2024-08-15 ⋅ 阅读:(133) ⋅ 点赞:(0)

题目背景

约翰厌倦了劳作的生活,决定将遗产分给两个儿子,然后云游四方(约翰很疼爱两个儿子,但是偏心大儿子)。

题目描述

约翰是一个农场主,他的农场有 n 块田,编号从 1 到 n,这 n 块田通过 m 条双向道路相连(数据保证这n块田都是联通的),我们假设第 i 块田会产生 2ikg 的收益,现在约翰想把农田的工作全部交给自己的两个孩子,划分方式必须满足以下规则:

  • 1.每一块田都需要恰好被分给一个孩子.
  • 2.分给两个孩子的农田必须是联通的.就是说对于任意一个孩子在划分给自己的任意一块田,都可以不经过另外一个孩子的田,到达自己的任意一块田.
  • 3.划分给两个孩子的收益必须尽可能的相等,如果无法相等,年长的孩子会得到大的那一份.

对于第 ii 块田,如果你要把它分给年长的孩子,请输出A,否则输出B.

输入格式

第一行输入两个整数分别代表 n,mn,m

接下来 mm行,每个两个整数u,vu,v,代表这两块农田通过一条双向道路直接相连,数据保证没有自环

输出格式

输出一个长度为 nn 的字符串,代表答案

样例

输入数据 1

3 2
1 3
3 2

Copy

输出数据 1

ABA

Copy

提示

样例解释

我们发现此样例无法使得收益相等,那么于是我们将第 11 和 第 33 块农田分给长子,第 22 块农田分给小儿子,可以使得收益差距最小。

数据范围

2≤n≤3×105,1≤m≤3×1052≤n≤3×105,1≤m≤3×105

可以使用深度优先搜索(DFS)算法对图中的节点进行标记的 C++ 程序。它接受输入的节点数和边数,以及边的信息。然后,它使用DFS算法根据节点的连通性将节点标记为'A'或'B'。

该程序使用一个向量的向量来表示图,使用一个数组 'a' 来存储节点的标记。DFS函数用于根据节点与最后一个节点的连通性来标记节点。

  1. 程序接受输入的图中节点数和边数。
  2. 然后,它接受边的输入并相应地填充图。
  3. 将最后一个节点的标记初始化为 'A',并调用DFS函数来标记其他节点。
  4. DFS函数根据节点与最后一个节点的连通性来标记节点。
  5. 最后,程序打印所有节点的标记。

代码:

 

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5; 
vector<int>g[N];
int n,m,a[N];
void dfs(int x){
	if(a[x]==1){
		return;
	}
	a[x]=2;
	for(auto to:g[x]){
		if(!a[to]){
			dfs(to);
		}
	}
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	a[n]=1;
	dfs(n-1);
	for(int i=1;i<=n;i++){
		if(a[i]==2){
			cout<<'B';
		}else{
			cout<<'A';
		}
	}
    return 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到