最小生成树
Kruskal+ufs
int ufs(int x) {
return f[x] == x ? x : f[x] = ufs(f[x]);
}
int Kruskal() {
int w = 0;
for(int i=0; i<n; i++)
f[i] = i;
sort(e, e+n);
for(int i=0; i<n; i++) {
int x = ufs(e[i].u), y = ufs(e[i].v);
if(x != y) {
f[x] = y;
w += e[i].w;
}
} return w;
}
Prim
int Prim() {
int w = 0;
priority_queue<pair<int, int> > q;
bool l[N] = {0};
l[1] = 1; q.push(make_pair(0, 1));
for(int k=1; k<n; k++) {
int u = q.top().second; q.pop();
for(int i=0; i<G[u].size(); i++)
if(!l[G[u][i]])
q.push(make_pair(-c[u][i], G[u][i]));
while(!q.empty() && l[q.top().second])
q.pop();
l[q.top().second] = 1;
w += -q.top().first;
q.pop();
} return w;
}
最短路径
Dijkstra+priority_queue
void Dijkstra(int s) {
priority_queue<pair<int, int> > q;
bool l[N] = {0}; l[s] = 1;
fill_n(f, n, INF); f[s] = 0;
q.push(make_pair(-f[s], s));
while(!q.empty()) {
int u = q.front().second; q.pop();
for(int i=0; i<G[u].size(); i++) {
int v = G[u][i];
if(f[v] > f[u] + c[u][i]) {
f[v] = f[u] + c[u][i];
if(!l[v]) {
l[v] = 1;
q.push(make_pair(-f[v], v));
}
}
}
}
}
Bellman-Ford (SPFA)
void BellmanFord(int s) { // SPFA
queue<int> q;
bool l[N] = {0}; l[s] = 1;
fill_n(f, n, INF); f[s] = 0;
q.push(s);
while(!q.empty()) {
int u = q.front(); q.pop();
l[u] = 0;
for(int i=0; i<G[u].size(); i++) {
int v = G[u][i];
if(f[v] > f[u] + c[u][i]) {
f[v] = f[u] + c[u][i];
if(!l[v]) {
l[v] = 1;
q.push(v);
}
}
}
}
}
Floyd
void Floyd() {
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
二分图
ufs 验证
Hungary
bool DFS(int u) {
for(int i=0; i<G[u].size(); i++) {
int v = G[u][i];
if(!l[v]) {
l[v] = 1;
if(!f[v] || DFS(f[v])) {
f[v] = u;
return true;
}
}
} return false;
}
int Hungary() {
int w = 0;
for(int i=0; i<n; i++) {
fill_n(l, l+n, 0);
if(DFS(i))
w++;
} return w;
}
连通分量
Tarjan
stack<int> s;
void Tarjan(int u) {
dfn[u] = low[u] = ++time;
l[u] = 1;
s.push(u);
for(int i=0; i<G[u].size(); i++) {
int v = G[u][i];
if(!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if(l[v])
low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
w++;
do {int v;
l[v = s.top()] = 0;
f[v] = w;
s.pop();
} while(u != v);
}
}
void SCC() {
fill_n(dfn, n, 0);
for(int i=0; i<n; i++)
if(!dfn(i))
Tarjan(i);
}
*网络流
最大流：Edmonds-Karp
费用流：Bellman-Ford 找增广路，或者用贪心求解