当前位置:网站首页>登山小分队(dfs)
登山小分队(dfs)
2022-07-07 05:38:00 【why151】
题目描述:
主要思路:
开始看这个题目没看清楚,以为是每个人可以任意选一条路向上爬。
后来发现是每一条路上边一个人,然后我就没有思路了。
因为我不知道怎么判断那条路面临着同时过两个人的问题。
然后我看了dalao的代码,还是倒着从1开始,每次每条路从下一个节点往上上一个人,我觉得很妙!
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int num[1010];
vector<int> l[1010];
int f[1010];//记录每个点上有几个人
//每个节点上的一个人往上一个节点走一步
void dfs(int x,int last)
{
for(int i=0;i<l[x].size();i++)
{
int nowx=l[x][i];
if(nowx!=last)
{
if(f[nowx])
{
f[nowx]-=1;
f[x]+=1;
}
dfs(nowx,x);
}
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
l[x].push_back(y);
l[y].push_back(x);
num[x]+=1;
num[y]+=1;
}
int sum=0;
for(int i=2;i<=n;i++)
{
if(num[i]==1) f[i]=1,sum+=1;
}
int ans=0;
while(f[1]!=sum)
{
dfs(1,0);
ans+=1;
}
cout<<ans<<endl;
return 0;
}
边栏推荐
- 使用BiSeNet实现自己的数据集
- In go language, function is a type
- Improve the delivery efficiency of enterprise products (1) -- one click installation and upgrade of enterprise applications
- Grpc, oauth2, OpenSSL, two-way authentication, one-way authentication and other column directories
- The single value view in Splunk uses to replace numeric values with text
- Battery and motor technology have received great attention, but electric control technology is rarely mentioned?
- [Chongqing Guangdong education] audio visual language reference materials of Xinyang Normal University
- Transformation function map and flatmap in kotlin
- 国标GB28181协议视频平台EasyGBS新增拉流超时配置
- 【无标题】
猜你喜欢
[quick start of Digital IC Verification] 12. Introduction to SystemVerilog testbench (svtb)
Data type - integer (C language)
Analysis of maker education in innovative education system
Improve the delivery efficiency of enterprise products (1) -- one click installation and upgrade of enterprise applications
Explore creativity in steam art design
Download and install orcale database11.2.0.4
Openvscode cloud ide joins rainbow integrated development system
Tuowei information uses the cloud native landing practice of rainbow
Splunk query CSV lookup table data dynamic query
Coquette data completes the cloud native transformation through rainbow to realize offline continuous delivery to customers
随机推荐
单场带货涨粉10万,农村主播竟将男装卖爆单?
Data type - integer (C language)
Arm GIC (IV) GIC V3 register class analysis notes.
[machine learning] watermelon book data set_ data sharing
[go ~ 0 to 1] obtain timestamp, time comparison, time format conversion, sleep and timer on the seventh day
Famine cloud service management script
关于基于kangle和EP面板使用CDN
[kuangbin]专题十五 数位DP
Opencv learning note 5 - gradient calculation / edge detection
[quick start of Digital IC Verification] 12. Introduction to SystemVerilog testbench (svtb)
[quick start of Digital IC Verification] 14. Basic syntax of SystemVerilog learning 1 (array, queue, structure, enumeration, string... Including practical exercises)
Battery and motor technology have received great attention, but electric control technology is rarely mentioned?
Iptables' state module (FTP service exercise)
JEditableTable的使用技巧
Improve the delivery efficiency of enterprise products (1) -- one click installation and upgrade of enterprise applications
Caractéristiques de bisenet
Analyzing the influence of robot science and technology development concept on Social Research
Through the "last mile" of legal services for the masses, fangzheng Puhua labor and personnel law self-service consulting service platform has been frequently "praised"
Splunk子查询模糊匹配csv中字段值为*
Xcit learning notes