HalaMadrid！

分类

tarjan算法(7) 二分图(2) 未归档(22) 网络流(2) 读书笔记(4) 题解(11)

/ 注册

全部文章（共48篇）

4-（tarjan-给定一个有向图，求最大可以增加多少条边使得这个仍然不是强连通）

https://vjudge.net/problem/HDU-4635#author=634579757有t组数据，给了一个n个点m条边的有向图，问给此图最多加多少条边，满足如下条件:1：此图不能强连通2：没有重边和自环3：当图本身就是强连通的时候就输出-1那么现在我们考虑，如何加边使得加的边尽可能...

2020-10-29

1 657

3-（tarjan-使图中任意2点之间至少存在2条不同的路径-应该添加的路径数目）

https://vjudge.net/problem/POJ-3177#author=haomie思路：本质上就是用求边双连通分量的思路来求解；首先我们可以对图进行边连通分量缩点，缩点后图就会变成一颗树，代表任意2点之间的路径是唯一的。这时候题目转化为添加最少的边使任意2点的路径至少有2条。结...

2020-10-28

1 519

2-（tarjan-DAG-最少从几个点出发能够走遍全图-最少加上几条边能够该图变为强连通图)

https://vjudge.net/problem/POJ-1236思路：一个DAG上从入度为0的点出发一定可以走遍当前DAG, 所以第一问输出入度为0的点的个数对于一个DAG, 入度为0的一定是起点, 出度为0的一定是终点. 仔细思考一下, 如果只有一个起点显然应该加一条边, 如果只有一个终点...

2020-10-28

1 631

1-（tarjan-求联通块个数-分别列举去掉每个点的情况）

https://ac.nowcoder.com/acm/contest/7501/D思路：用Tarjan算法的思路来写，dfn[i]代表结点 i 的dfs序，low[i]代表从结点 i dfs下去能到达的dfn值最小的结点的dfn值。若x为当前结点，y为一个x的未被访问过的子节点，若对 y dfs完...

2020-10-28

1 665

算法记录-5-（欧拉路问题）

欧拉回路算法概况：书本上原理的实现时间复杂度：O（n+m） #include<iostream> using namespace std; int head[100010],ver[1000010],Next[1000010],tot; int stack[1000010],ans[10...

2020-10-26

0 0

算法记录-3-（LCA）

树上倍增法算法概况：基于动态规划，适用于多次查询时间复杂度：O((n+m)logn) #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<c...

2020-10-24

0 0

算法记录-2-（线段树-扫描线）

https://ncc79601.blog.luogu.org/scan-line题目链接：https://vjudge.net/problem/POJ-1151有时候一篇好的题解真的救人命，扫描线的原理一看就会，但代码实现着实费了老大功夫。上上下下找了不少题解，要么晦涩难懂，要么码风实在劝退。 ...

2020-10-19

1 0

算法记录-1-（次小生成树-Kru解法）

例题：https://vjudge.net/problem/POJ-1679算法描述：关于次小生成树，首先求出最小生成树，然后枚举每条不在最小生成树上的边（在原本的节点上添加一个vis属性进行判断即可），并把这条边放到最小生成树上面，然后就一定会形成环，那么我们在这条环路中取出一条（除了新加入的那一...

2020-10-15

0 0

2020 Multi-University Training Contest 2(补题)

Lead of Wisdomhttp://acm.hdu.edu.cn/showproblem.php?pid=6772暴力搜索，但是要稍微优化一下，特别是num[x]==0的情况要在dfs前预处理一下； #include<iostream> #include<algorithm&...

2020-08-28

1 480

2020牛客暑期多校训练营（第六场）（补题）

Binary Vectorhttps://ac.nowcoder.com/acm/contest/5671/B这题主要考察逆元和线代知识，具体思路见下方： #include<cstdio> const int mod=1e9+7,inv=5e8+4; int ans[20000005]...

2020-08-28

0 572