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

标签 分层图 下的文章

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...
October 31, 2019

洛谷P3831/SHOI2012 回家的路

题意$n \times n$的网格图中有$m$个点可转向,求最短路数据范围:$n \le 20000,m \le 100000$题解分层图两层图,每层只建一种方向的边(纵/横),连接两层之间表示转向代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring&g...
October 31, 2019

洛谷P1948/USACO08JAN 电话线Telephone Lines

题意无向图中,可选择$k$条边将边权变为$0$,求最小瓶颈最短路数据范围:$1 \le n,k \le 1000,1 \le m \le 10000$题解分层图每层内建原图,在层之间建边权为$0$的单向边,意为一次变化,因此共$k+1$层为统计答案,由每一层的终点向超级汇点连一条权值为$0$的单向边代码:#include<iostream> #include<cstdio&...
October 27, 2019

洛谷P3119/USACO15JAN 草鉴定Grass Cownoisseur

题意给出一张有向图,可以逆行$1$次,求从$1$回到$1$最多经过几个点数据范围:$1 \le n,m \le 100000$题解首先$\mathrm{Tarjan}$缩点,并将新点点权赋为所在强连通分量的点数新图建分层图,连接两层之间为反向边,意为逆行$1$次从$1$所在的强连通分量开始跑$\mathrm{SPFA}$最长路,答案即为到第二层中$1$所在的强连通分量对应的点的距离代码:#i...
October 12, 2019

洛谷P4568/JLOI2011 飞行路线

题意无向图中,可选择$k$条边将边权变为$0$,求最短路数据范围:$2 \le n \le 10000,1 \le m \le 50000,0 \le k \le 10$题解分层图每层内建原图,在层之间建边权为$0$的单向边,意为一次变化,因此共$k+1$层为统计答案,由每一层的终点向超级汇点连一条权值为$0$的单向边代码:#include<iostream> #include&...