ゆめぼくらでって
きたるべきのためによる

标签 图论 下的文章

November 1, 2019

洛谷P4171/JSOI2010 满汉全席

题意略数据范围:$n \le 100,m \le 1000$题解容易想到这是一个$\text{2-SAT}$问题将每种材料拆成满/汉两种选择,分别为$i,i+n$,每个评审的要求可以看作“或”建图跑$\text{Tarjan}$,判断$i,i+n$是否在同一强连通分量里代码:#include<iostream> #include<cstdio> #include<...
November 1, 2019

洛谷P4630/APIO2018 Duathlon 铁人两项

题意无向图中,求三元组$(s,c,f)$的个数,使得从$s \rightarrow v \rightarrow f$为简单路径数据范围:$n \le 100000,m \le 200000$题解可以发现,答案就是路径上可能经过的点数将图缩成圆方树,统计树上路径点数若将方点点权标为点双大小,圆点点权标为$-1$,则某条路径上的答案就是圆方树上两点之间的点权和因为枚举点对是$O(n^2)$的,所...
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 31, 2019

洛谷P1768 天路

题意最优比率环数据范围:$1 \le n \le 7000,1 \le m \le 20000$题解$0/1$分数规划要求$$ans=\frac{\sum_i^{i \in E} v_i}{\sum_i^{i \in E} p_i}$$二分这个答案$mid$,将每条边的边更改为$$mid \cdot p_i-v_i$$跑负环即可代码:#include<iostream> #in...
October 31, 2019

洛谷P2850/USACO06DEC 虫洞Wormholes

题意判负环数据范围:$1 \le n \le 500,1 \le m \le 2500$题解$\text{dfs SPFA}$判负环即可代码:#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=510; const int M=5210...
October 31, 2019

洛谷P1849/USACO12MAR 拖拉机Tractor

题意略数据范围:$1 \le n \le 50000$题解优先队列$\text{bfs}$,以移动的干草堆数升序代码:#include<iostream> #include<cstdio> #include<queue> using namespace std; #define mp make_pair typedef pair<int,int>...
October 31, 2019

CF786B Legacy

题意有$3$种连边方式$u \rightarrow v$ 点向点$u \rightarrow [l,r]$ 点向区间$[l,r] \rightarrow u$ 区间向点求从$s$出发的最短路数据范围:$1 \le n,q \le 10^5$题解显然对于向区间建边不能一个一个建,那么能不能直接向整个区间建边呢?联想到线段树的一个节点维护一个区间的信息,那么可以向这个节点建边;这便是线段树优化建...