minux_sufe

分类

算法(2) 题解(28)

/ 注册

全部文章（共30篇）

tarjan缩点找出拓扑图中的最长链

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=100005; const int M=2000005; const LL P=1000007; // hash code ...

scc 图论 tarjan 缩点

2020-07-02

0 488

tarjan缩点

#include <bits/stdc++.h> using namespace std; const int N=105; const int M=10005; int n; int head[N], E=0; // 邻接表建图 int dfn[N], low[N], ts=0; ...

scc 图论 tarjan 缩点

2020-07-01

0 414

tarjan缩点

#include <bits/stdc++.h> using namespace std; const int N=10005; const int M=50005; int n, m, E=0, scc_cnt=0; int head[N], id[N], sz[N], dout[N...

scc 图论 tarjan 缩点

2020-07-01

0 493

倍增LCA求解

#include <bits/stdc++.h> using namespace std; const int N=100005; const int M=N*2; int n, m; struct Edge{ int v, ne; }e[M]; int depth[N], ...

LCA 倍增

2020-07-01

0 606

倍增LCA

#include <bits/stdc++.h> using namespace std; const int N=40005; const int M=2*N; int head[N], depth[N], fa[N][16]; // 2^16-1=65535>40000 可...

LCA 倍增

2020-06-30

0 551

在线建图SPFA

#include <bits/stdc++.h> using namespace std; const int N=30; const int M=80; // 统计出差分系统方程组的个数不超过80个 const int K=1005; int a[N], r[N], dist[N],...

图论前缀和

2020-06-29

0 531

SPFA求解

#include <bits/stdc++.h> using namespace std; const int N=1005; const int M=10005+10005+1005; const int INF=0x3f3f3f3f; int n, m1, m2, E=0; in...

图论

2020-06-29

0 580

kruskal求解

问题需要转化一下思路，转化为找一个权值, 当去掉权值的边后, 剩余的连通块的数量要. #include <bits/stdc++.h> using namespace std; const int N=505; // NC上本题数据范围缺失, 从LOJ上查询到1<=n<=5...

图论

2020-06-24

0 455

区间DP (2)

问题链接: 能量项链思路: 区间DP 环形区间展开为链式区间, 定义f[i][j]表示区间[i,j]的能量转移方程为f[i][j]=f[i][k]+f[k][j]+a[i]*a[k]*a[j] 算法设计 python from typing import List class Solution: ...

动态规划

2020-05-14

0 482

区间DP (1)

问题链接: 环形石子合并思路: 区间DP 区间处理题目中给出了一个环状区间, 如果考虑贪心算法, 可以找到反例; 如果对区间缺口进行枚举, 那么时间复杂度为.一种常用的优化技巧为复制一倍区间, 将环状区间转为链式区间存储, 枚举长度为的区间, 优化后的时间复杂度为. 动态规划状态定义: f[l]...

动态规划前缀和

2020-05-14

0 500