Deep_Kevin的娱乐空间

正题      第二题：上白泽慧音      这道题就是裸裸的Tarjan强联通咯~      我们找出每个环，判断一下每个环的大小。排一下序输出即可。代码<模板要背熟>#include<cstdio> #include<cstdlib> #include<cstring> #include<vector> #include<sta...

正题      [HAOI2006]受欢迎的牛      其实这道题就是求缩点之后，入度为0的环的大小。      我们跑一便Tarjan缩点之后，记录每个点所在环的编号和大小即可。#include<cstdio> #include<cstdlib> #include<cstring> #include<stack> #include<vect...

正题      [POI2008]BLO-Blockade      这一题很神奇啊~      我们来想想两个点不能连通和强连通有什么关系。      那么其实很明显，如果当前点所遍历到的子节点不能遍历到祖先节点，那么说明子节点只能通过该点来去到祖先节点，这样产生的有序点对数量就是son[x]*(n-son[x]-1)*2，（假设当前点为x，则儿子节点即为son[x]）      所以可以延伸出...

正题      [USACO5.3]校园网Network of Schools      第一问：求至少从多少个节点开始，可以遍历整个图。      第二问：求至少加上多少条边，使得无论从哪个节点开始，都可以遍历整张图      首先声明先缩环成点。      第一问就是求入度为0的点即可，因为不是入度为0的话，那么肯定可以从另外一个点传递信息过来。      第二问好像很烦，要求的是加上多少条边...

正题      [USACO15JAN]草鉴定Grass Cownoisseur      这一题好像很烦，因为要处理“反向走一次”这个东西。      但是我们好像枚举就可以啊~~      首先要缩点，因为环内的两个节点都可以互相到达。      缩完点之后，我们就想，怎么才可以满足这个条件。      其实就是要想，建一条边之后成环嘛.      那么反转一条边后所形成环的大小就等于1所在连...

正题      [HNOI2012]矿场搭建      点双连通分量？？边双连通分量？？      不懂？？     其实这题也没那么麻烦，代码也没那么长~     我们先找割点，然后分类讨论一下。     我们dfs找出与当前节点（枚举）在同一连通块的点，如果是割点就不用往下搜了，那么我们求出来的就是，割点被炸掉之后的连通分块。     当 当前连通分块的割点有两个及以上时，那么无论炸掉那个点，...