当前位置:网站首页>POJ 3140 contents division "suggestions collection"
POJ 3140 contents division "suggestions collection"
2022-07-07 20:59:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
The main idea of the topic :
Give me a tree . Find the minimum value of the sum of the node weights of the two subtrees after removing an edge .
Their thinking :
I don't know how to use tree DP do , It's just a DFS It's over . I hit back once .
Think about the code in detail .
Here's the code :
#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;
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116301.html Link to the original text :https://javaforall.cn
边栏推荐
- Jetty:配置连接器[通俗易懂]
- [matrix multiplication] [noi 2012] [cogs963] random number generator
- openGl超级宝典学习笔记 (1)第一个三角形「建议收藏」
- Intelligent software analysis platform embold
- Is it safe to open an account of BOC shares in kainiu in 2022?
- I Basic concepts
- 目前股票开户安全吗?可以直接网上开户吗。
- C语言 整型 和 浮点型 数据在内存中存储详解(内含原码反码补码,大小端存储等详解)
- 恶魔奶爸 A3阶段 近常速语流初接触
- You want to kill a port process, but you can't find it in the service list. You can find this process and kill it through the command line to reduce restarting the computer and find the root cause of
猜你喜欢
智能软件分析平台Embold
最新版本的CodeSonar改进了功能安全性,支持MISRA,C ++解析和可视化
H3C s7000/s7500e/10500 series post stack BFD detection configuration method
Nebula importer data import practice
Klocwork code static analysis tool
解决使用uni-app MediaError MediaError ErrorCode -5
C language helps you understand pointers from multiple perspectives (1. Character pointers 2. Array pointers and pointer arrays, array parameter passing and pointer parameter passing 3. Function point
Helix QAC 2020.2新版静态测试工具,最大限度扩展了标准合规性的覆盖范围
Onespin | solve the problems of hardware Trojan horse and security trust in IC Design
C语言 整型 和 浮点型 数据在内存中存储详解(内含原码反码补码,大小端存储等详解)
随机推荐
DataTable数据转换为实体
Lex & yacc of Pisa proxy SQL parsing
使用枚举实现英文转盲文
复杂因子计算优化案例:深度不平衡、买卖压力指标、波动率计算
Is private equity legal in China? Is it safe?
Details of C language integer and floating-point data storage in memory (including details of original code, inverse code, complement, size end storage, etc.)
Apifox 接口一体化管理新神器
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your
CodeSonar通过创新型静态分析增强软件可靠性
Codeforces Round #296 (Div. 2) A. Playing with Paper[通俗易懂]
Airiot helps the urban pipe gallery project, and smart IOT guards the lifeline of the city
神兵利器——敏感文件发现工具
Network principle (1) - overview of basic principles
Klocwork 代码静态分析工具
Phoenix JDBC
Measure the height of the building
恶魔奶爸 B1 听力最后壁垒,一鼓作气突破
使用高斯Redis实现二级索引
华泰证券可以做到万一佣金吗,万一开户安全嘛
Small guide for rapid formation of manipulator (11): standard nomenclature of coordinate system