HalaMadrid！

分类

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

/ 注册

全部文章（共48篇）

滑动窗口-区间最值（模板）

ps:遗忘了原理，可以参考下文https://www.acwing.com/solution/content/2499/ #include<iostream> #include<algorithm> #include<cstdio> #include<cst...

2020-11-23

0 545

__int128 输入输出（模板）

//适用范围可达39位 #include <bits/stdc++.h> using namespace std; inline __int128 read(){ __int128 x=0,f=1; char ch=getchar(); while(ch<...

2020-11-21

0 1017

2020ICPC 江西省大学生程序设计竞赛（finished）

https://ac.nowcoder.com/acm/contest/8827L:WZB's Harem1.状态压缩+dfs，保存结果从而实现剪枝；2.状压dp，思路非常直接，不多说，相对更快 F:Magical Number简单dfs，容易看出，木棍足够多时，无法找到满足条件的数字，故搜索范围并...

2020-11-17

0 804

算法记录-9-（Dinic算法-最大流）

时间复杂度：O(n^2m)Dinic是比较容易实现的效率最高的网络流算法之一，一般能够处理10^4~10^5规模的网络 #include<iostream> #include<cstring> #include<queue> #include<cstdio&...

2020-11-02

0 679

算法记录-8-（Edmonds-Karp增广路算法-最大流）

时间复杂度：O(nm^2)一般能够处理10^3-10^4规模的网络 #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; c...

2020-11-02

1 663

6-（KM算法-求带权最小匹配

https://vjudge.net/problem/POJ-3565思路：所有线段都不相交，等价于让每条线段的长度之和最小至于求最小匹配，只要把边权w[][]取反，然后按求最大匹配的思路求解即可 #include<iostream> #include<cstdio> #in...

2020-11-01

0 762

算法记录-7-（二分图带权最大匹配-KM算法）

时间复杂度：O（N^4）本算法局限性较大，只能在满足“带权最大匹配一定是完备匹配”的图中正确求解，所以一般使用费用流来求解此类问题，但是本算法在求解稠密图时效率要高于费用流 const int N=105; int w[N][N]; int la[N],lb[N]; bool va[N],vb[N]...

2020-11-01

0 978

算法记录-6-（tarjan-有向图连通性）

tarjan-强连通分量 #include<iostream> #include<cstring> #include<vector> using namespace std; const int N=100010,M=1000010; int ver[M],Nex...

2020-11-01

0 450

算法记录-4-（tarjan-无向图连通性）

tarjan--求一张无向图中所有的桥》》书上的样例 #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; cons...

2020-11-01

0 571

5-（tarjan-结合题目条件-寻找权值最小的桥）

https://vjudge.net/problem/HDU-4738#author=Dillydally思路： 1.注意重边处理。2.守卫为0时，也需要派一个人；3.如果原本图不连通，就不需要派人。4.然后直接输出桥的最小边权就可以了。相对简单，详情不再赘述 #include<iostrea...

2020-10-29

1 530