当前位置:网站首页>POJ 3140 Contestants Division「建议收藏」
POJ 3140 Contestants Division「建议收藏」
2022-07-07 20:58:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
题目大意:
给出一棵树。求去掉一条边之后两棵子树节点权值和作差的最小值。
解题思路:
这不知道怎么用树形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;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116301.html原文链接:https://javaforall.cn
边栏推荐
- Tensorflow2. How to run under x 1 Code of X
- 寫一下跳錶
- Lex & yacc of Pisa proxy SQL parsing
- 论文解读(ValidUtil)《Rethinking the Setting of Semi-supervised Learning on Graphs》
- Can Huatai Securities achieve Commission in case of any accident? Is it safe to open an account
- Optimization cases of complex factor calculation: deep imbalance, buying and selling pressure index, volatility calculation
- Apifox 接口一体化管理新神器
- Implement secondary index with Gaussian redis
- Codesonar enhances software reliability through innovative static analysis
- 想杀死某个端口进程,但在服务列表中却找不到,可以之间通过命令行找到这个进程并杀死该进程,减少重启电脑和找到问题根源。
猜你喜欢
H3C S7000/S7500E/10500系列堆叠后BFD检测配置方法
AADL inspector fault tree safety analysis module
Lex & yacc of Pisa proxy SQL parsing
Helix QAC 2020.2 new static test tool maximizes the coverage of standard compliance
Make this crmeb single merchant wechat mall system popular, so easy to use!
Optimization cases of complex factor calculation: deep imbalance, buying and selling pressure index, volatility calculation
神兵利器——敏感文件发现工具
目标:不排斥 yaml 语法。争取快速上手
【论文阅读】MAPS: Multi-agent Reinforcement Learning-based Portfolio Management System
Mysql子查询关键字的使用方式(exists)
随机推荐
【函数递归】简单递归的5个经典例子,你都会吗?
写一下跳表
Nebula Importer 数据导入实践
使用高斯Redis实现二级索引
The latest version of codesonar has improved functional security and supports Misra, c++ parsing and visualization
静态测试工具
万字总结数据存储,三大知识点
【矩阵乘】【NOI 2012】【cogs963】随机数生成器
MySQL storage expression error
uva 12230 – Crossing Rivers(概率)「建议收藏」
Is it safe to open an account of BOC shares in kainiu in 2022?
华泰证券可以做到万一佣金吗,万一开户安全嘛
Make this crmeb single merchant wechat mall system popular, so easy to use!
恶魔奶爸 A0 英文零基础的自我提升路
easyui 日期控件清空值
Écrivez une liste de sauts
Static analysis of software defects codesonar 5.2 release
Data sorting in string
Tensorflow2. How to run under x 1 Code of X
Codeforces 474 F. Ant colony