LYNX

Links

Tags

Categories

oj

树的遍历

morris算法(中序遍历)

空间复杂度$O(1)$

void print_out(node *cur);// 输出节点

node *find_prev(node *cur);// 寻找前驱节点

void morris(node *root) {
node *cur = root;
while (cur != NULL) {// 没有遍历完
if (cur->left == NULL) {// 1: cur没有左子节点
print_out(cur);
cur = cur->right;
} else {
node *prev = find_prev(cur);
if (prev->right == NULL) {// 2.1: prev没有右子节点
prev->right = cur;// 修改树结构
cur = cur->left
} else if (prev->right == cur) {// 2.2: prev的右子节点为cur
prev->right = NULL;// 恢复树结构
print_out(cur);
cur = cur->right;
} else {
assert(0);
}
}
}
}

图的遍历

DFS

void dfs(node u) {
u.visit = 1;
for (int i = 0; i < u.adj.size(); i ++) {
node v = u.adj[i];
if (v.visit == 0) {
dfs(v);
}
}
}

BFS

void bfs() {
q.push(s);
while (q.empty() == 0) {
node u = q.top();
q.pop();
for (int i = 0; i < u.adj.size(); i ++) {
node v = u.adj[i];
if (v.visit == 0) {
v.depth = u.depth + 1;
q.push(v);
}
}
}
}

连通度

tarjan算法

时间复杂度$O(V+E)$

void tarjan(int x) {
s.push(x);
depth ++;
dfn[x] = depth;// dfs标记
low[x] = depth;// tarjan标记
in_stack[x] = 1;// 是否入栈
int u, v;
for (int i = 0; i < near[x].size(); i ++) {
int v = near[x][i].v;
if (dfn[v] == 0) {// 未被标记过
tarjan(v);
low[x] = my_min(low[x], low[v]);
} else if (in_stack[v] == 1) {// 已经入栈
low[x] = my_min(low[x], dfn[v]);// my_min(low[x], low[v])l
}
}

if (dfn[x] == low[x]) {// 强连通分量
block ++;// 连通块数目
while (s.empty() == 0) {
v = s.top();
in_stack[v] = 0;
s.pop();
if (v == x) break;
}
}
}

网络流

EK算法

时间复杂度$O(VE^2)$

dinic算法

时间复杂度$O(V^2E)$

struct path {
public:
int u;// 起点
int v;// 终点
int c;// 容量
int f;// 流量
int back;// 反向边编号

path() {
f = 0;
}
};
int T, n, m;
int path_num;
int s, t;
int level[MAXN];// 分层
vector<int> near[MAXN];// 邻接表
path paths[MAXM];// 所有edge

void add_path(int u, int v, int c) {
// 正向边
paths[path_num].u = u;
paths[path_num].v = v;
paths[path_num].c = c;
paths[path_num].f = 0;
paths[path_num].back = path_num + 1;
near[u].push_back(path_num);
path_num ++;
// 反向边
paths[path_num].u = v;
paths[path_num].v = u;
paths[path_num].c = 0;
paths[path_num].f = 0;
paths[path_num].back = path_num - 1;
near[v].push_back(path_num);
path_num ++;
}

int dfs(int x, int flow) {
if (x == t) return flow;
int total_flow = 0;
for (int i = 0; i < near[x].size(); i ++) {
int forward = near[x][i];
int v = paths[forward].v;
int w = paths[forward].c - paths[forward].f;
if (w > 0 && level[v] == level[x] + 1) {
int extend = dfs(v, my_min(w, flow - total_flow));
if (extend > 0) {
int backward = paths[forward].back;
paths[forward].f += extend;
paths[backward].f -= extend;
total_flow += extend;
}
}
}
return total_flow;
}

int bfs() {
queue<int> que;
memset(level, 0, sizeof(level));
que.push(s);
level[s] = 1;
while (que.empty() == 0) {
int u = que.front();
que.pop();
for (int i = 0; i < near[u].size(); i ++) {
int forward = near[u][i];
int v = paths[forward].v;
int w = paths[forward].c - paths[forward].f;
if (w > 0 && level[v] == 0) {
level[v] = level[u] + 1;
que.push(v);
}
}
}
return level[t];
}

int dinic() {
int ans = 0;
while (1) {
if (bfs() == 0) break;// 没有增广路
ans += dfs(s, INF);
}
return ans;
}

匹配算法

最大匹配:匈牙利算法

时间复杂度$O(VE)$

vector<int> x_near[];// x的邻接表
int y_match[];// y的配对记录
int y_visit[];// 用于dfs的标记

void match() {
for (int i = 0; i < n; i ++) {// n为x个数
memset(y_visit, 0, sizeof(y_visit));
if (dfs(i)) {
ans ++;
}
}
}

int dfs(int x) {
for (int i = 0; i < x_near[x].size(); i ++) {
int index = x_near[x][i];
if (y_visit[index] == 0) {// 没有被dfs过的y
y_visit[index] = 1;
if (y_match[index] == -1 || dfs(y_match[index])) {
// 如果 (没有配对 || 已经配对的能够增广)
y_match[index] = x;// 为x找到新的配对
return 1;
}
}
}
return 0;
}

最优匹配:KM算法

int n;// 总数
int x_ex[MAXN];// x的期望
int y_ex[MAXN];// y的期望
int x_visit[MAXN];// 每轮配对时x的标记
int y_visit[MAXN];// 每轮配对时y的标记
int y_match[MAXN];// 与y配对的x
int y_slack[MAXN];// 每轮遍历x改变的期望
int near[MAXN][MAXN];// 邻接矩阵

int KM();
int dfs(int x);

int dfs(int x) {
assert(x > 0);
x_visit[x] = 1;
for (int i = 1; i <= n; i ++) {
if (y_visit[i] == 0) {
int gap = x_ex[x] + y_ex[i] - near[x][i];// 两者的期望和与实际值之差
if (gap == 0) {
// 符合要求
y_visit[i] = 1;// TODO
if (y_match[i] == 0 || dfs(y_match[i])) {
// 没有匹配 || 可以增广
y_match[i] = x;
return 1;
}
} else {
y_slack[i] = my_min(y_slack[i], gap);
}
}
}
return 0;
}

int KM() {
memset(x_ex, 0, sizeof(x_ex));
memset(y_ex, 0, sizeof(y_ex));// 无期望
memset(y_match, 0, sizeof(y_match));// 无配对

// 最大化x期望
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
x_ex[i] = my_max(x_ex[i], near[i][j]);
}
}

// 为每个x进行匹配
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {// 初始期望为无穷
y_slack[j] = INF;
}

while (1) {// 直到找到配对为止
memset(x_visit, 0, sizeof(x_visit));
memset(y_visit, 0, sizeof(y_visit));

int extend = dfs(i);
if (extend == 1) break;

// 找出最小的slack
int min_slack = INF;
for (int j = 1; j <= n; j ++) {
if (y_visit[j] == 0) {// 不符合要求的y(交错树之外)
min_slack = my_min(min_slack, y_slack[j]);
}
}

// 调整x, y的期望
for (int j = 1; j <= n; j ++) {
if (x_visit[j] == 1) {
x_ex[j] -= min_slack;
}
if (y_visit[j] == 1) {
y_ex[j] += min_slack;
}
}
}
}

// 计算和
int ans = 0;
for (int i = 1; i <= n; i ++) {
ans += near[y_match[i]][i];
}

return ans;
}

字符串匹配

KMP算法

void kmp() {// a[1], b[1]为起始项
// 计算前缀表
p_len = 0;
for (int i = 2; i <= m; i ++) {// 注意初始赋值
while (p_len && b[p_len + 1] != b[i]) {
p_len = kmp[p_len];
}
if (b[p_len + 1] == b[i]) {
p_len ++;
kmp[i] = p_len;
}
}
// 进行匹配
p_len = 0;
for (int i = 1; i <= n; i ++) {// 注意初始赋值
while (p_len && b[p_len + 1] != a[i]) {
p_len = kmp[p_len];
}
if (b[p_len + 1] == a[i]) {
p_len ++;
if (p_len == m) {
printf("%d\n", i - p_len + 1);
break;
}
}
}
}

Tags

bfs
dfs

Categories

1 / 1