您现在的位置是:首页 > 正文

poj3107(树的重心)

2024-04-01 07:13:02阅读 1
求树的重心。树的重心是指去掉重心之后剩下的子树的最大结点个数最少
树形DP,dp[i]表示以i为重心,剩下的子树的最大结点个数,状态转移dp[i] = max(dp[i], siz[j])。
注意用vector超时。

代码如下:

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<string>
#include<vector>

#define N 50005
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 10e-6

using namespace std;
int n,tot;
int siz[N],dp[N],head[N];
struct node
{
    int next,v,w;//next邻接表中的下一条边的编号,v边所到达的点,w权值
}edge[N*2];
void addedge(int u,int v)
{
    edge[tot].next = head[u];
    edge[tot].v = v;
    head[u] = tot++;
}
void dfs(int u,int pa)
{
    siz[u] = 1;
    dp[u] = 0;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == pa) continue;
        dfs(v,u);
        siz[u] += siz[v];
        dp[u] = max(siz[v],dp[u]);
    }
    dp[u] = max(dp[u], n-siz[u]);
}
int main()
{
    while(scanf("%d",&n) != EOF)
    {
        int i;
        memset(siz,0,sizeof(siz));
        memset(head,-1,sizeof(head));
        for(i = 1; i < n; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        tot = 0;
        dfs(1,0);
        int ans = inf;
        for(i = 1; i <= n; i++)     ans = min(ans,dp[i]);
        for(i = 1; i <= n; i++) if(ans ==  dp[i])   { printf("%d",i); break;}
        for(i = i+1; i <= n; i++)  if(ans == dp[i]) printf(" %d",i);
        printf("\n");

    }
    return 0;
}


网站文章

  • 基于可视化 BI 工具 DataEase 制作第七次人口普查数据分析大屏

    基于可视化 BI 工具 DataEase 制作第七次人口普查数据分析大屏

    基于可视化 BI 工具 DataEase 制作第七次人口普查数据分析大屏

    2024-04-01 07:12:55
  • jdk1.8创建stream的方法有哪些??

    jdk1.8创建stream的方法有哪些??

    环境:jdk1.8创建stream的方法常见的有:单线程(stream),多线程(parallelStream),Stream.of(),Stream.iterate()等等。详情见代码:public...

    2024-04-01 07:12:46
  • windowTranslucentStatus设置为true的坑

    原文地址:https://www.jianshu.com/p/f345f5715ecd windowTranslucentStatus是Android4.4(API为19)开始提供的样式设置,如果要想在4.4手机上做沉浸式状态栏那么直能设置true。在Android5.0以后的版本可以不用设置windowTranslucentStatus=true来做沉浸式状态栏,可以直接设置状态栏颜色。...

    2024-04-01 06:59:51
  • Idea集成Git

    Idea集成Git

    安装Git工具 Git是版本控制系统,可以借助Git实现团队代码版本控制及管理,从官方https://www.gitscm.com/downl…,如图所示: Git下载完成以后,傻瓜式(一直下一步)...

    2024-04-01 06:59:44
  • Android实现双进程守护

    Android实现双进程守护

    如何保证Service不被Kill有关Service的知识请参考Android Service全面解析这篇文章,写的很详细。(1)onStartCommand方法,返回START_STICKY@Override public int onStartCommand(Intent intent, int flags, int startId) { flags = START_STICKY

    2024-04-01 06:59:37
  • 2021-07-22

    2021-07-22

    前言 Ubuntu16.04 安装 ROS时,有时在运行sudo rosdep init后出现下所示错误: (图1)rosdep init ROS安装问题 首先试着通过浏览器访问error中提及的网址...

    2024-04-01 06:58:56
  • C++ PASCAL关键字(转)

    VC里面:PASCAL==CALLBACK==WINAPI==__stdcall _stdcall是Pascal程序的缺省调用方式,通常用于Win32 Api中,函数采用从右到左的压栈方式,自己在退出时清空堆栈。VC将函数编译后会在函数名前面加上下划线前缀,在函数名后加上"@"和参数的字节数。 _cdecl是C和C++程序的缺省调用方式。每一个调用它的函数都包含清空堆...

    2024-04-01 06:58:49
  • Spring Boot 发送邮件全解析

    Spring Boot 发送邮件全解析

    1.前言 今天我们就来学一下如何在Spring Boot下发送电子邮件。 2. 依赖 Java 发送邮件依赖jakarta项目(原javaEE)提供的jakarta.mail组件,Maven坐标: com.sun.mail jakarta.mail ...

    2024-04-01 06:58:42
  • STM32CubeIDE中文

    STM32CubeIDE中文

    【Windows】——【Preferences】——【General】——【Appearance】——【Colors and Fonts】——【Edit】——【把“西欧字符”改成“中欧字符”】如果你在...

    2024-04-01 06:58:00
  • 基于SpringBoot+MyBatis实现的个人博客系统(一)

    基于SpringBoot+MyBatis实现的个人博客系统(一)

    基于SpringBoot+MyBatis实现的个人博客系统(一)

    2024-04-01 06:57:54