标签：打板子 诈尸 int register head vis low 赛前 dis
图论
存图
链式前向星
$Code$
struct Graph{
int cnt;
int head[MAXN];
Graph(){
cnt = 0;
memset(head, 0, sizeof(head));
}
struct Edge{
int to, next, dis;
}e[MAXN];
inline void Add(int u, int v, int w){
e[++cnt].to = v;
e[cnt].dis = w;
e[cnt].next = head[u];
head[u] = cnt;
}
}G;
最短路
\(\mathit{Floyed}\)
$Code$
void Floyed(){
for(register int k = 1; k <= n; k++){
for(register int i = 1; i <= n; i++){
for(register int j = 1; j <= n; j++){
if(k == i || k == j || i == j) continue;
if(map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j];
}
}
}
}
\(\mathit{SPFA}\)
$Code$
void Spfa(int u){
queue<int> q;
memset(dis, 0x3f, sizeof(dis));
q.push(u), dis[u] = 0, vis[u] = true;
while(!q.empty()){
int t = q.front();
for(register int i = G.head[t]; i; i = G.e[i].next){
int v = G.e[i].to;
if(dis[v] > dis[t] + G.e[i].dis){
dis[v] = dis[t] + G.e[i].dis;
if(!vis[v]) q.push(v), vis[v] = true;
}
}
vis[t] = false;
q.pop();
}
}
堆优化 \(\mathit{Dijkstra}\)
$Code$
struct Road{
int pos, dis;
bool operator < (const Road &a) const{
return dis > a.dis;
}
};
priority_queue< Road, vector<Road>, greater<Road> > q;
void Dijkstra(int u){
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0, q.push((Road){u, 0});
while(!q.empty()){
int t = q.top().pos;
q.pop();
if(vis[t]) continue;
vis[t] = true;
for(register int i = G.head[t]; i; i = G.e[i].next){
int v = G.e[i].to;
if(dis[v] > dis[t] + G.e[i].dis){
dis[v] = dis[t] + G.e[i].dis;
if(!vis[v]) q.push((Road){v, dis[v]});
}
}
}
}
最小生成树
\(\mathit{Prim}\) 算法
$Code$
struct Road{
int pos, dis;
bool operator < (const Road &a) const{
return dis > a.dis;
}
};
priority_queue< Road, vector<Road>, greater<Road> > q;
void Prim(){
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
q.push((Road){1, dis[1]});
while(!q.empty() && tot < n){
int k = q.top().pos;
q.pop();
if(used[k]) continue;
tot++;
sum += dis[k];
used[k] = true;
for(register int i = head[k]; i; i = e[i].next){
int v = e[i].to;
if(dis[v] > e[i].dis){
dis[v] = e[i].dis;
q.push((Road){v, dis[v]});
}
}
}
}
\(\mathit{Kruskal}\) 算法
$Code$
struct Line{
int from, to, dis;
}line[MAXM];
bool cmp(const Line &a, const Line &b){
return a.dis < b.dis;
}
struct Union_Set{
int fa[MAXN];
void init(int n){
for(register int i = 1; i <= n; i++) fa[i] = i;
}
int Find(int x){
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
}U;
void Kruskal(){
U.init(n);
sort(line + 1, line + 1 + m, cmp);
for(register int i = 1; i <= m; i++){
int u = line[i].from, v = line[i].to;
int fa_u = U.Find(u), fa_v = U.Find(v);
if(fa_u != fa_v){
++tot;
U.fa[fa_u] = fa_v;
G.Add(u, v, line[i].dis), G.Add(v, u, line[i].dis);
}
if(tot == n - 1) break;
}
}
\(\mathit{Tarjan}\)
求强连通分量及缩点
$Code$
void Tarjan(int u){
low[u] = dfn[u] = ++num;
vis[u] = true;
stk[++top] = u;
for(register int i = G.head[u]; i; i = G.e[i].next){
int v = G.e[i].to;
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[v]){
++tot; int t;
do{
t = stk[top--];
vis[t] = false;
belong[t] = tot;
}while(t != u);
}
}
void Rebuild(){
G.cnt = 0;
memset(G.head, 0, sizeof(G.head));
for(register int i = 1; i <= m; i++){
int u = from[i], v = to[i];
if(belong[u] != belong[v]) G.Add(u, v);
}
}
求割点
$Code$
void Tarjan(int u){
dfn[u] = low[u] = ++num;
int son = 0;
for(register int i = G.head[u]; i; i = G.e[i].next){
int v = G.e[i].to;
if(!dfn[v]){
++son;
Tarjan(v);
low[u] = min(low[u], low[v]);
if(dfn[u] <= low[v]){
if(son > 1 || u != root) cut[u] = true;
}
}
else low[u] = min(low[u], dfn[v]);
}
}
求点双联通分量
$Code$
void Tarjan(int u, int fa){
dfn[u] = low[u] = ++num;
vis[u] = true, stk[++top] = u;
int son = 0; bool first = true;
for(register int i = G.head[u]; i; i = G.e[i].next){
int v = G.e[i].to;
if(first && v == fa){
first = false;
continue;
}
if(!dfn[v]){
++son;
Tarjan(v, u);
low[u] = min(low[u], low[v]);
if(dfn[u] <= low[v]){
cut[u] = true;
++tot;
point[tot].push_back(u);
int t;
do{
t = stk[top--];
point[tot].push_back(u);
}while(t != u);
}
}
else low[u] = min(low[u], dfn[v]);
}
if(!fa && son == 1) cut[u] = false;
}
二分图
匈牙利算法
$Code$
bool dfs(int u){
for(register int i = G.head[u]; i; i = G.e[i].next){
int v = G.e[i].to;
if(!vis[v]){
vis[v] = true;
if(!match[v] || dfs(match[v])){
match[v] = u;
return true;
}
}
}
return false;
}
int Hungary(){
int ans = 0;
for(register int i = 1; i <= n; i++){
memset(vis, 0, sizeof(vis));
if(dfs(i)) ++ans;
}
return ans;
}
\(\mathit{Kruskal}\) 重构树
$Code$
struct Line{
int from, to, dis;
}line[MAXM];
bool cmp(const Line &a, const Line &b){
return a.dis < b.dis;
}
struct Union_Set{
int fa[MAXN];
void init(int n){
for(register int i = 1; i <= n; i++) fa[i] = i;
}
int Find(int x){
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
}U;
void Kruskal(){
int tot = 0; sum = n, G.cnt = 0;
memset(G.head, 0, sizeof(G.head));
U.init(n << 1);
sort(line + 1, line + 1 + m, cmp);
for(register int i = 1; i <= m; i++){
int u = line[i].from, v = line[i].to;
int fa_u = U.Find(u), fa_v = U.Find(v);
if(fa_u != fa_v){
++tot;
val[++sum] = line[i].dis;
G.Add(fa_u, sum), G.Add(sum, fa_u);
G.Add(fa_v, sum), G.Add(sum, fa_v);
U.fa[fa_u] = U.fa[fa_v] = sum;
}
if(tot == n - 1) break;
}
}
标签：打板子,
诈尸,
int,
register,
head,
vis,
low,
赛前,
dis
From： https://www.cnblogs.com/TSTYFST/p/17139035.html