题意有 $n(\le 100)$ 个软件可以安装,每个软件会占 $w_i$ 的磁盘空间,价值为 $v_i$ ,每个软件都有至多一个依赖。剩余磁盘空间为 $m(\le 500)$ ,问安装软件的价值最大值。题解环上的软件必须要全装才有收益,所以先缩点。然后把 $0$ 看成树根,并将它与无依赖的软件连边。剩下的就是标准的树形背包问题,只是注意当前枚举的软件一定会安装,否则无法安装子树上的软件。#...
题意一个有向图,求:至少选多少个起点才可以遍历整个图至少加几条边,能满足从任意一个点出发都能遍历整张图其中点数 $N\le 100$ 。题解显然可以先缩点,然后对题意进行转化:入度为 $0$ 的点的个数加最少的边,让整张图成一个环问题 $1$ 很显然,对于问题 $2$ ,可以把所有入度为 $0$ 和出度为 $0$ 的节点相连,所以答案即为两者的较大值。#include<bits/std...
题意给一个无向图,要求任意两个点之间都至少有两条相离的路径,求最少的连边数。其中点数 $N\le 5000$ ,边数 $M\le 10000$ 。题解显然环上的节点都满足这个要求,所以题目可以理解成要求所有节点都在环上,那么可以先把已经有的环缩点。缩完点后就变成了一棵树,要让所有点在环上,那么把所有叶子节点之间两两连接即可。当然叶子节点也有可能有奇数个,所以需要连边的个数为 $(leaf+1...
题意给出一个有点权的无向图,有的节点有酒吧。从起点出发,需要找到以酒吧为终点的路径,每个节点可以经过任意次,求路径上点权和的最大值。其中点数 $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[]$ ,并删...