洛谷3959 [NOIP2017]宝藏

题目大意

给你$n$个点,$m$条边,要你选一个点作为根建一棵生成树满足代价最小

一棵生成树的代价是$\Sigma \; dep[i] * dis[fa_i][i]$, 其中$dep_i$表示$i$节点在这棵生成树中的深度(根节点深度为$0$,$dis[fa_i][i]$表示$i$节点到他父亲节点的距离

题目大意

给你$n,f_1,f_2,f_3,c$,让你求$f_n=c^{2n-6} \times f_{n-1} \times f_{n-2} \times f_{n-3}$

设$f_u$表示$u$不被以$u$为根的子树内点(包括$u$)通上电的概率,则有:

$$f_u=(1-p_u) \times \prod_{v \in subtree \; u}e(u, v) \times f_v$$

洛谷4314 cpu监控

首先我们可以想到一个显而易见的思路:每个节点维护$\mathrm{add,set}$的$tag$,维护最大值$max$和历史最大值$Max$,然后像正常的线段树一样维护

然后你惊讶的发现你只拿到二十分(只有$Q$的部分分)

为什么呢?我们发现有些$tag$,他还没有来得及被更新就被覆盖了..而这些$tag$本来能改变世界更新答案

所以我们可以维护两个$tag$:$\mathrm{Add,Set}$表示该节点从上次下放到目前的最大$add$和$set$值

然后我们就可以快乐的用这些$tag$来维护答案了

建模:

1.从$s$向人$1-n$连边,容量为$1$,费用为$0$

2.从工作$1-n$向$t$连边,容量为$1$,费用为$0$

3.从人$1-n$向工作$1-n$连边,容量为$1$,费用为$c_{i,j}$

枚举答案,对于$(i,j)(i<j)$,若$i<j$且$i+j$是完全平方数,则从$i$向$j$连一条边

然后跑最小路径覆盖(可以参照LOJ 6002)

方案输出也类似上一题

1.建立两个集合$x$和$y$

2.如果有一条边$<u,v>$,则从$x$集合中的$u$点连向$y$集合的$v$点,容量为$inf$

3.从$s$向$x$中每一个点连边,从$y$中每一个点向$t$连边,容量为$1$

和LOJ #6004圆桌聚餐很像

建模:

1.从源点向每道试题$x_i$连一条容量为$1$的边

2.从每种类型$y_i$向汇点连一条容量为该类型需求数量的边

3.如果试题$x_i$属于类型$y_i$则从$x_i$向$y_i$连一条容量为$1$的边

然后跑裸的网络最大流,如果最大流$\not=$需求试题总数则无解

方案:

对于每种类型,它连出的所有满流量边即为该类型所对应的试题

建模:

1.从源点向每个单位$x_i$连边,容量是该单位的人数

2.从每张餐桌$y_i$向汇点连边,容量是该餐桌能容纳的人数

3.从每个单位$x_i$向每张餐桌$y_j$连边,容量为$1$

如果最大流量等于所有单位人数之和,则有解,否则无解。

方案:

对于每个单位$x_i$,该单位向$y$集合连出的所有满流量边即为该单位人员的安排情况(证明显然

很简单的网络流

对于每个正飞行员,从源点向它连一条容量为$1$的边

对于每个副飞行员,从它向汇点连一条容量为$1$的边

对于每一对可以配对的正/副飞行员,从正飞行员向副飞行员连一条容量为$1$的边

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×