正文 

当前位置： 首页 > IT > java教程

p2986[usaco10mar]伟大的奶牛聚集(代码片段)

-ackerman -ackerman     2023-04-17     773

关键词：

题意：

给一棵 n 个点的边 + 点权树，求带权重? 
 

思路：

其实这题和之前那个 Sta 有点像，我们同样只需要预处理出一个 f[u] 代表以 u 为集合点的方便程度，那么我们就可以O（1）的转移了

假设 v 是 u 的儿子，f[v] = f[u] - (siz[v] * len) + (n - siz[v] ) * len = f[u] + (n - 2 * siz[v] )  * len

这题有一个坑，就是你的INF得开的特别大，不然你就没有 100 了

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <math.h>
#include <cstdio>
#include <iomanip>
#include <time.h>
#include <bitset>
#include <cmath>

#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f
#define ls nod<<1
#define rs (nod<<1)+1

const double eps = 1e-10;
const int maxn = 1e5 + 10;
const LL mod = 1e9 + 7;

int sgn(double a)return a < -eps ? -1 : a < eps ? 0 : 1;
using namespace std;

struct edge 
    int v,nxt,w;
e[maxn << 1];

int head[maxn];
LL siz[maxn],dis[maxn],num[maxn],f[maxn];
int cnt,n;
LL ans;

inline void add_edge(int u,int v,int w) 
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;


inline void dfs(int u,int f) 
    siz[u] = num[u];
    for (int i = head[u];~i;i = e[i].nxt) 
        int v = e[i].v,len = e[i].w;
        if (v == f)
            continue;
        dis[v] = dis[u] + len;
        dfs(v,u);
        siz[u] += siz[v];
    


inline void func(int x,int fa) 
    for (int i = head[x];~i;i = e[i].nxt) 
        int v = e[i].v,len = e[i].w;
        if (v == fa)
            continue;
        f[v] = f[x] - siz[v] * len + (siz[1] - siz[v]) * len;
        func(v,x);
    


int main() 
    memset(head,-1, sizeof(head));
    cnt = 0;
    ans = INF;
    cin >> n;
    for (int i = 1;i <= n;i++) 
        cin >> num[i];
    
    for (int i = 1;i < n;i++) 
        int u,v,w;
        cin >> u >> v >> w;
        add_edge(u,v,w);
        add_edge(v,u,w);
    
    dfs(1,0);
    for (int i = 1;i <= n;i++) 
        f[1] += (dis[i]*num[i]);
    
    func(1,0);
    for (int i = 1;i <= n;i++) 
        ans = min(ans,f[i]);
    
    cout << ans << endl;
    return 0;

 

p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)

题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然， 查看详情

p2986[usaco10mar]伟大的奶牛聚集（思维，dp）(代码片段)

题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方... 查看详情

p2986[usaco10mar]伟大的奶牛聚集greatcowgat…

典型树上dp，直接暴力算会超时，小心呀    #include<cstring>#include<iostream>#include<algorithm>#include<cstdio>#include<vector>#definemaxn100010usingnamespacestd;typedeflonglongll;structNode intp; lllen; Node(inta,llb):p(a),len(b);vec... 查看详情

p2986[usaco10mar]伟大的奶牛聚集(代码片段)

题意：给一棵n个点的边+点权树，求带权重?  思路：其实这题和之前那个Sta有点像，我们同样只需要预处理出一个f[u]代表以u为集合点的方便程度，那么我们就可以O（1）的转移了假设v是u的儿子，f[v]=f[u]-(siz[v]*len)+(n-siz[v])... 查看详情

p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)

　　一道比较经典的题（蒟蒻的我没有一次切掉）……　　首先这道题要优化的原因就是数据范围，要是O(n2) “ 显然 ”会超时。。。　　那么我们很不情愿不得已不开心地最终被迫考虑一下优化（说实话好多算法都... 查看详情

[usaco10mar]伟大的奶牛聚集

[USACO10MAR]伟大的奶牛聚集Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路... 查看详情

洛谷p2986[usaco10mar]greatcowgat…(树形dp+容斥原理)

P2986[USACO10MAR]伟大的奶牛聚集GreatCowGat…题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace. 查看详情

bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)

【题解】　　很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。　　我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。　　显然选择它的儿子... 查看详情

[usaco10mar]伟大的奶牛聚集-树形dp(代码片段)

每个点有重数，求到所有点距离最小的点就是魔改的重心了#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1000005;vector<pair<int,int>>g[N];intsiz[N],f[N],vis[N],sum[N],c[N],n,m,t1,t2,t3,tot;voiddfs1(intp)vis[p]=1;siz[p]=c[p];for(inti=0;i<... 查看详情

bzoj1703[usaco2007mar]rankingthecows奶牛排名*

bzoj1703[Usaco2007Mar]RankingtheCows奶牛排名题意：n头奶牛，知道n对奶牛之间的产奶量大小，问想知道所有奶牛产奶量大小顺序至少还需知道几对。n≤1000。题解：每个大小关系看为一条有向边，对每头奶牛进行dfs，求每头奶牛可以到... 查看详情

bzoj3375[usaco2004mar]paranoidcows发疯的奶牛*

bzoj3375[Usaco2004Mar]ParanoidCows发疯的奶牛题意：依次给出n只奶牛的产奶时间段，求最大的k使得前k只奶牛不存在一个时间段被另一个时间段完全覆盖的情况。n≤100000。题解：设当前在处理第i只奶牛，前i-1只奶牛都合法。那么如果... 查看详情

[bzoj]1657:[usaco2006mar]mooo奶牛的歌声

1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec  MemoryLimit:64MBSubmit:858  Solved:603[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverystraigh 查看详情

[bzoj]1616:[usaco2008mar]cowtravelling游荡的奶牛

1616:[Usaco2008Mar]CowTravelling游荡的奶牛TimeLimit: 5Sec  MemoryLimit: 64MBSubmit: 1312  Solved: 736[Submit][Status][Discuss]Description奶牛们在被划分成N行M列(2<=N<=100 查看详情

[bzoj1657][usaco2006mar]mooo奶牛的歌声

 1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec  MemoryLimit:64MBSubmit:863  Solved:607[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverys 查看详情

[usaco2010mar]gather奶牛大集会

[Usaco2010Mar]gather奶牛大集会题目Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条... 查看详情

[bzoj]1657:[usaco2006mar]mooo奶牛的歌声

1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit: 5Sec  MemoryLimit: 64MBSubmit: 867  Solved: 610[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsa 查看详情

洛谷p3052[usaco12mar]摩天大楼里的奶牛cowsinaskyscraper

P3052[USACO12MAR]摩天大楼里的奶牛CowsinaSkyscraper题目描述AlittleknownfactaboutBessieandfriendsisthattheylovestairclimbingraces.Abetterknownfactisthatcowsreallydon‘tlikegoingdownstairs.Soafterthecowsfinishracingt 查看详情

bzoj3401[usaco2009mar]lookup仰望*

bzoj3401[Usaco2009Mar]LookUp仰望题意：约翰的N头奶牛站成一排，奶牛i的身高是Hi。对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j。求出每只奶牛离她最近的仰望对象。n≤100000.题解：用一个单调栈维护即可... 查看详情