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)


相关推荐

  • pagecontext request session_pagecontent

    pagecontext request session_pagecontent ${pageContext.request.contextPath}是JSP取得绝对路径的方法,等价于&lt;%=request.getContextPath()%&gt; 。 也就是取出部署的应用程序名或者是当前的项目名称 比如我的项目名称是demo1在浏览器中输入为http://localhost:8080/demo1/a.jsp${pageContext.request.co…

  • JAVA设计模式之单例模式

    本文继续介绍23种设计模式系列之单例模式。概念:  java中单例模式是一种常见的设计模式,单例模式的写法有好几种,这里主要介绍三种:懒汉式单例、饿汉式单例、登记式单例。  单例模式有以下特点:  1、单例类只能有一个实例。  2、单例类必须自己创建自己的唯一实例。  3、单例类必须给所有其他对象提供这一实例。  单例模式确保某个类只有一个实例,而且自行实例化并向整个系统提供这个实例…

  • ubuntu 卸载软件命令_linux卸载软件包命令

    ubuntu 卸载软件命令_linux卸载软件包命令彻底删除软件sudoapt-getpurgeXXX 清楚残留sudoapt-getautoremove        sudoapt-getclean

  • 播放ipod歌曲

    播放ipod歌曲

  • 好东西!

    好东西!

  • 在线视频下载网址合集

    在线视频下载网址合集视频鱼:http://m.shipinyu.cn/微博党:http://weibodang.cn/index硕鼠:http://www.flvcd.com/微博秒拍视频解析下载:https://weibo.iiilab.com/短视频解析下载:http://dy.ck921.com/飞狐视频下载:https://www.3987.com/dsp/ks.html兔兔解析:http://w…

发表回复

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

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