标签:图论-缩点

题意有 $n(\le 100)$ 个软件可以安装,每个软件会占 $w_i$ 的磁盘空间,价值为 $v_i$ ,每个软件都有至多一个依赖。剩余磁盘空间为 $m(\le 500)$ ,问安装软件的价值最大值。题解环上的软件必须要全装才有收益,所以先缩点。然后把 $0$ 看成树根,并将它与无依赖的软件连边。剩下的就是标准的树形背包问题,只是注意当前枚举的软件一定会安装,否则无法安装子树上的软件。#...
题意一个有向图,求:至少选多少个起点才可以遍历整个图至少加几条边,能满足从任意一个点出发都能遍历整张图其中点数 $N\le 100$ 。题解显然可以先缩点,然后对题意进行转化:入度为 $0$ 的点的个数加最少的边,让整张图成一个环问题 $1$ 很显然,对于问题 $2$ ,可以把所有入度为 $0$ 和出度为 $0$ 的节点相连,所以答案即为两者的较大值。#include<bits/std...
算法竞赛 图论-Tarjan 图论-缩点
题意给一个无向图,要求任意两个点之间都至少有两条相离的路径,求最少的连边数。其中点数 $N\le 5000$ ,边数 $M\le 10000$ 。题解显然环上的节点都满足这个要求,所以题目可以理解成要求所有节点都在环上,那么可以先把已经有的环缩点。缩完点后就变成了一棵树,要让所有点在环上,那么把所有叶子节点之间两两连接即可。当然叶子节点也有可能有奇数个,所以需要连边的个数为 $(leaf+1...
算法竞赛 图论-Tarjan 图论-缩点
题意给出一个有点权的无向图,有的节点有酒吧。从起点出发,需要找到以酒吧为终点的路径,每个节点可以经过任意次,求路径上点权和的最大值。其中点数 $N\le 500000$ ,边数 $M\le 500000$ 。题解缩点,转化为DAG后跑最长路即可。最后取有酒吧的节点中最长路的最大值。#include<bits/stdc++.h> using namespace std; inl...
题意定义半连通图为对于 $\forall (u,v)$ ,存在从 $u$ 到 $v$ 或从 $v$ 到 $u$ 的有向路径。给出一个有向图,求最大半连通子图中的节点个数以及最大半连通子图的个数。其中点数 $N\le 100000$ ,边数 $M\le 1000000$ 。题解显然连通图也属于半连通图,那么可以先缩点,记录每个点的新编号 $scc[]$ 以及包含节点个数 $siz[]$ ,并删...
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划52 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP16 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP3 图论4 图论-LCA4 图论-Tarjan11 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束4 图论-强连通分量2 图论-最小环1 图论-最小生成树6 图论-最短/最长路19 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点5 图论-负环4 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集2 数据结构-栈1 数据结构-树状数组6 数据结构-树链剖分10 数据结构-线段树5 数据结构-队列1 比赛-Codeforces21 比赛-JX Round1 比赛-NOIp/CSP5 算法-KM算法1 算法-二分/三分12 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序2 算法-排序3 算法-搜索21 算法-模拟5 算法-状态压缩4 算法-贪心10 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2