POJ 3140 Contestants Division「建议收藏」

POJ 3140 Contestants Division

大家好,又见面了,我是全栈君。

题目大意:

给出一棵树。求去掉一条边之后两棵子树节点权值和作差的最小值。


解题思路:

这不知道怎么用树形DP做,仅仅是个DFS就过了。还手残了一次。

思路详细看代码。



以下是代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <map>
#include <queue>
using namespace std;

int min(int a,int b)
{
    if(a>b)a=b;
    return a;
}
int max(int a,int b)
{
    if(a<b)a=b;
    return a;
}
struct node
{
    int to,next;
} edge[100005*2];
int n,m,cnt,head[100005];
long long weight[100005],min1,sum;
const long long inf = 100000000000000ll;
bool vis[100005];
void addedge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
bool chack(int src)
{
    int t=head[src];
    while(t!=-1)
    {
        if(!vis[edge[t].to])return true;
        t=edge[t].next;
    }
    return false;
}
long long llaabs(long long num)
{
    if(num<0)num=-num;
    return num;
}
long long dfs(int src)
{
    long long ans=weight[src],temp;
    vis[src]=true;
    if(chack(src))
    {
        int t=head[src];
        while(t!=-1)
        {
            if(!vis[edge[t].to])
            {
                temp=dfs(edge[t].to);
                min1=min(min1,llaabs(sum-temp-temp));
                ans+=temp;
            }
            t=edge[t].next;
        }
    }
    return ans;
}
int main()
{
    int case1=1;
    while(scanf("%d%d",&n,&m),n||m)
    {
        cnt=0;
        int u,v;
        min1=inf;
        sum=0;
        memset(vis,false,sizeof(vis));
        memset(head,-1,sizeof(head));
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&weight[i]);
            sum+=weight[i];
        }
        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
        }
        dfs(1);
        printf("Case %d: %lld\n",case1++,min1);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116301.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • APK签名原理

    APK签名原理网上已有多篇分析签名的类似文章,但是都有一个共同的问题,就是概念混乱,混乱的一塌糊涂。在了解APK签名原理之前,首先澄清几个概念:消息摘要-MessageDigest简称摘要,请看英文翻译,是摘要,不是签名,网上几乎所有android签名分析的文章都对这两个概念乱用摘要的链接http://en.wikipedia.org/wiki/Message_digest简

  • java 堆栈的声明_Java 堆栈[通俗易懂]

    java 堆栈的声明_Java 堆栈[通俗易懂]Java堆栈堆栈是一种线性数据结构,用于存储对象的集合。它基于先进先出(LIFO)。Java集合框架提供了许多接口和类来存储对象的集合。其中之一是Stack类,它提供了不同的操作,例如推,弹出,搜索等。在本节中,我们将讨论JavaStack类,其方法和实现在Java中的堆栈数据结构程序。但是在转到JavaStack类之前,请先快速了解堆栈的工作原理。堆栈数据结构具有两个最重要的操作,分别…

  • 掌握这些常用Linux命令,一起提升工作效率

    万字长文分享Linux常用命令,一起提升工作效率。开始上班了,新一年的奋斗的之路启程了,要继续【奔赴山海,奔赴热爱】。

  • 吐血整理!java面试中经常被问到的问题「建议收藏」

    吐血整理!java面试中经常被问到的问题「建议收藏」主备同步的实现原理我们先来了解一下主备同步的原理,下面以一个update语句来介绍主库与备库间是如何进行同步的。上图是一个update语句在节点A执行,然后同步到节点B的完整流程图,具体步骤有:主库接受到客户端发送的一条update语句,执行内部事务逻辑,同时写binlog。备库通过changemaster命令,设置主库的IP、端口、用户名和密码,以及要从哪个位置开始请求binlog。这个位置包含文件名和偏移量。在备库上执行startslave命令,启动两个线程io_thread

  • Qt实现抽奖程序

    Qt实现抽奖程序一、简介该程序命名为Lucky,实现的功能如下:1.加载抽奖人员名单,并保存加载路径;2.单击左键或者点击ctrl+s开始抽奖,并滚动显示人员名单,显示的人员名单格式为部门-姓名。3.

  • 论坛提问智慧

    论坛提问智慧本文转载自http://bbs.weblogicfans.net/thread-3628-1-1.html.一、确定你自己无法解决该问题 首先你至少应该解决问题花费1个小时以上的时间,并最终确定自己无力解决。问题的解决并不能够完全依靠他人。二、查看论坛精华文章 你遇到的问题很有可能已经有文章详细的论述如何解决了,精华文章往往是大家最需要留心关注的地方。 三、使用

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号