正文

洛谷2458(代码片段)

せみしぐれ  せみしぐれ  2022-11-11  502

关键词：

f[now][0]表示以当前点为根，且要取该点，满足条件的最小

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
int head[1501],to[1501],nex[1501],val[1501],indg[1501],f[1501][3],n,cnt,rt;

inline void read(int &x)
    char ch=getchar();x=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar(); 


void addedge(int u,int v)
    to[++cnt]=v;nex[cnt]=head[u];head[u]=cnt;


void dfs(int now)
    if(!head[now])f[now][0]=f[now][1]=val[now];f[now][2]=0;return;
    f[now][0]=val[now];f[now][2]=0;
    for(int i=head[now];i;i=nex[i])
        dfs(to[i]);
        f[now][0]+=min(f[to[i]][1],min(f[to[i]][2],f[to[i]][0]));
        f[now][2]+=min(f[to[i]][0],f[to[i]][1]);
    f[now][1]=1e9;
    for(int i=head[now];i;i=nex[i])
        f[now][1]=min(f[now][1],f[now][2]-min(f[to[i]][0],f[to[i]][1])+f[to[i]][0]);
    


int main()
    read(n);
    for(int i=1;i<=n;i++)
        int u,som,v;read(u);read(val[u]);read(som);
        while(som--)read(v);indg[v]++;addedge(u,v);
    
    for(int i=1;i<=n;i++)if(!indg[i])rt=i;break;
    dfs(rt);
    printf("%d",min(f[rt][0],f[rt][1]));

f[now][1]表示以当前点为根，至少取它的一个儿子，满足条件的最小值
f[now][2]表示他的儿子均被覆盖，满足条件的最小值
f[now][0]=val[now]+segma(min(f[son][0~2]));
f[now][1]=min(f[now][2]-min(f[son][0~1])+f[son][0])
f[now][2]=segma(f[son][0~1])
再注意叶子节点的赋值即可

[luogu2458][sdoi2006]保安站岗(代码片段)

题目描述五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望... 查看详情

(leetcode)2458.移除子树后的二叉树高度(代码片段)

link题意n个点的树,m次询问.询问的形式为割掉以x点为根的子树,求此时树的最大高度.首先树的高度一定在叶子节点取到而以x为根的子树包含的叶子节点设为v1,v2,v3…vx显然这些叶子节点的dfs序是一个连续的区间.于是可以直接把所... 查看详情

(leetcode)2458.移除子树后的二叉树高度(代码片段)

luogup2458[sdoi2006]保安站岗(代码片段)

显而易见树形dp然而我做了很很很很很久最后看讨论版才de出来bug要考虑三个状态1.父节点有保安2.本身有保安3.儿子节点放保安1.2.douhenhaokaolv3.不太容易，看了题解才有思路dp[u][2]：点u没有放置警察，且目前未被任何节点控制。所... 查看详情

洛谷3348(代码片段)

可持久化线段树模板1.结构体的打法#include<cstdio>#include<cctype>#include<algorithm>usingnamespacestd;constintmaxn=200010;structdataintl,r,sz;tr[maxn<<5];intn,m,cnt,key,a[maxn],rk[maxn],id[m 查看详情

求细胞数量-洛谷(代码片段)

求细胞数量-洛谷法1：BFS#include<iostream>#include<cstdio>usingnamespacestd;intdx[4]=-1,0,1,0;intdy[4]=0,1,0,-1;//左、右、上、下intbz[100][100],num=0,n,m;voiddoit(intp,intq)intx,y,t,w,i; 查看详情

洛谷p1535游荡的奶牛(代码片段)

P1535游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBessie‘spo 查看详情

洛谷p1816忠诚(代码片段)

https://www.luogu.org/problemnew/show/1816st表模板#include<cstdio>#include<algorithm>usingnamespacestd;typedeflonglongLL;LLm,n;LLa[100100],d[100100][20];intmain()LLi,j,l,r,k;scanf("%lld%lld" 查看详情

一个洛谷material化的stylish主题(代码片段)

一个将洛谷MaterialDesign化的主题。发布在stylish上，地址：https://userstyles.org/styles/157651/material-luogu-material欢迎发送issue截图代码最新代码请到stylish主题页面查看。https://userstyles.org/styles/157651/material-luogu-material@-moz-do 查看详情

洛谷1525关押罪犯——二分(代码片段)

题目：https://www.luogu.org/problemnew/show/P1525二分答案+二分图染色。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;typedeflonglongll;intn,m,head[20005],xnt,x,y;llans,l,r,z 查看详情

洛谷1608路径统计(代码片段)

【题解】　　最短路计数的模板题吧。。要把重边判掉。。　　1#include<cstdio>2#include<algorithm>3#defineN20104#definergregister5usingnamespacestd;6intn,m,tot=0,dis[N],pos[N],last[N],cnt[N],rec[N][N][11];7structedge8int 查看详情

洛谷p2888[usaco07nov]牛栏cowhurdles(代码片段)

　　　　　　　　　　　　　　　　　　　　洛谷 P2888[USACO07NOV]牛栏CowHurdles题目描述FarmerJohnwantsthecowstoprepareforthecountyjumpingcompetition,soBessieandthegangarepracticingjumpingoverhurdles.Theyaregettingtired,though, 查看详情

洛谷p1160双向链表(代码片段)

题目洛谷P1160代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;structnodeintL,R;a[N];voidinsert_left(intx,intk)//将x插入到k的左边a[x].R=k;a[x].L=a[k].L;a[a[k].L].R= 查看详情

洛谷p3403(代码片段)

跳楼机神仙建模题。Description一栋有\\(h\\)层的楼，初始位置为\\(1\\)，有如下操作：向上移动\\(x\\)层；向上移动\\(y\\)层；向上移动\\(z\\)层；回到\\(1\\)层。问可以到达的楼层数。Solution首先数据\\(h\\le2^63-1\\)暴搜显然不行。然后就... 查看详情

洛谷3768：简单的数学题——题解(代码片段)

https://www.luogu.org/problemnew/show/P3768题面来自洛谷，因为没用markdown所以直接截的图。剩余的图是我用markdown写完然后截的图。参考洛谷第一篇题解。这个式子直观感受就需要莫比乌斯反演，大致的过程参考：BZOJ2693：jzptab那么跳过... 查看详情

洛谷p1878舞蹈课贪心堆(代码片段)

洛谷P1878舞蹈课贪心堆1#include<bits/stdc++.h>2#defineLLlonglong3#defineGGint4#defineFor(i,j,k)for(registerinti=j;i<=k;i++)5#defineDow(i,j,k)for(registerinti=j;i>=k;i--)6usingnamespacestd;7inlineGG 查看详情

洛谷1462通往奥格瑞玛的道路(代码片段)

题目：https://www.luogu.org/problemnew/show/P1462二分答案。为什么djkstra不行，spfa可以？#include<iostream>#include<cstdio>#include<cstring>#include<queue>#definelllonglongusingnamespacestd;cons 查看详情