夢に僕らで帆を張って
来るべき日のために夜を超え


November 11, 2019

洛谷P3177/HAOI2015 树上染色

题意有一棵点数为$N$的树,树边有边权。给你一个在$0 \sim N$之内的正整数$K$,你要在这棵树中选择$K$个点,将其染成黑色,并将其他 的$N-K$个点染成白色将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少数据范围:$0 \le k \le n \le 2000$题解因为计算答案时需要对整颗树考虑,而一条边的贡献为$$一侧的黑/白色点数...
November 11, 2019

洛谷P1270 “访问”美术馆

题意经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画题解树上背包注意读入代码:#include<iostre...
November 11, 2019

洛谷P2014 选课

题意现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程$a$是课程$b$的先修课即只有学完了课程$a$,才能学习课程$b$)。一个学生要从这些课程里选择$M$门课程学习,问他能获得的最大学分是多少?数据范围:$1 \le n,m \le 300$题解树上背包用$dp[u][i]$表示以$u$为根的子树中选择$j$门课的最大学分代码:#include<iostream&...
November 11, 2019

洛谷P1122 最大子树和

题意求树上联通块的最大权值和数据范围:$n \le 16000$题解树形$\text{dp}$用$dp[u]$表示以$u$为根的子树中的最大权值和代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; co...
November 11, 2019

CF543B Destroying Roads

题意在这个国家有$n$个城市,城市间由$m$条双向公路连接。城市被编号为$1$到$n$ 。如果城市$a$和$b$被公路连接,那么你可以双向通行。你可以在这个公路网上通过公路从一个城市移动到另一个城市。走过每条公路均耗时$1$小时你想要破坏最多的公路,但是破坏后必须满足从指定城市$s_1$ 到$t_1$最短不超过$l_1$小时,且从指定城市$s_2$到$t_2$最短不超过$l_2$​ 小时计算...
November 11, 2019

CF449B Jzzhu and Cities

题意$n$个点,$m$条带权边的无向图,另外还有$k$条特殊边,每条边连接$1$和$i$问最多可以删除这$k$条边中的多少条,使得每个点到$1$的最短距离不变数据范围:$1 \le n,k \le 10^5,1\le m \le 3\times 10^5$题解最短路计数,判断这几条边是否再最短路上或这几个点有没有别的最短路可以达到代码:#include<iostream> #in...
November 9, 2019

洛谷P4015 运输问题

题意有$m$个仓库和$n$个零售商店。第$i$个仓库有$a_i$个单位的货物;第$j$个零售商店需要$b_j$个单位的货物从第$i$个仓库运送每单位货物到第$j$个零售商店的费用为$c_{ij}$试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少数据范围:$1 \le n,m \le 100$题解建立超级源点与超级汇点由超级源点向每个仓库建流量为$a_i$,费用为$0$的边...
November 9, 2019

洛谷P4009 汽车加油行驶问题

题意略数据范围:$2 \le n \le 100,2 \le k \le 10$题解将油量视为状态,分层建图之后跑最短路即可(也可跑费用流)代码:#include<iostream> #include<cstdio> #include<queue> #include<memory.h> using namespace std; const in...