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

标签 图论 下的文章

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...
November 6, 2019

洛谷P2633 Count on a tree

题意给出一棵带点权的树,$m$个询问,求$u \rightarrow v$路径上第$k$小的点权数据范围:$n,m \le 100000$ [强制在线]题解树上静态区间第$k$小,使用主席树维护序列上的主席树使用的是前缀和思想;那么自然,在树上的情况就要用到树上前缀和建树的时候在其父节点的基础上拷贝包含$u \rightarrow v$路径上的信息的应为$$T[u]+T[v]-T[lca(u...
November 5, 2019

洛谷P4151/WC2011 最大XOR和路径

题意给出一张无向图,求$1 \rightarrow n$的最大异或和路径数据范围:$n \le 50000,m \le 100000,d_i \le 10^{18}$题解考虑没有环的情况,答案为$dis[n]$若存在环,由于从$1 \rightarrow n$的路径上到环上的路径需要走两遍(去/回),相当于没有计算因此统计图上环的异或和,再与$dis[n]$异或求最大值而多个值异或的最大值可...
November 3, 2019

洛谷P3183/HAOI2016 食物链

题意给出$n$个物种和$m$条关系,求食物链条数数据范围:$1 \le n \le 100000,0 \le m \le 200000$题解记忆化搜索食物链从入度为$0$的点开始,到出度为$0$的点结束注意单独的一种孤立生物不算一条食物链代码:#include<iostream> #include<cstdio> using namespace std; const ...