问题求解3OJ模板

其实做题的时候大部分模板都是从CP那抄来的。

最小生成树

每次删除MST的一条边,跑$m$次,如果出现重复的权重说明MST不唯一。

Kruskal ($O(m \lg n)$)

void makeSet(int i) {
  fa[i] = i;
}

int findSet(int i) {
  if (i == fa[i]) return i;
  else return fa[i] = findSet(fa[i]);
}

void unionSets(int i, int j) {
  fa[findSet(i)] = findSet(j);
}

void kruskal() {
  for (int i = 0; i < n; ++i) {
    makeSet(i);
  }
  sort(edges.begin(), edges.end());
  for (Edge e : edges) {
    if (find_set(e.u) != findSet(e.v)) {
      cost += e.weight;
      result.push_back(e);
      unionSets(e.u, e.v);
    }
  }
}

Prim ($O(m \lg n)$)

void prim() {
  for (int i = 0; i < n; ++i) {
    int v = -1;
  }
  for (int j = 0; j < n; ++j) {
    if (!vis[j] && (v == -1 || min_e[j].w < min_e[v].w)) {
      v = j;
    }
  }

  // if (min_e[v].w == INF) NO MST

  vis[v] = true;
  cost += min_e[v].w;
  result.push_back({v, min_e[v].to});
  for (int to = 0; to < n; ++to) {
    if (adj[v][to] < min_e[to].w) {
      min_e[to] = {adj[v][to], v};
    }
  }
}

单源最短路径

Dijkstra (dense: $O(n^2+m)$)

void dijkstra() {
  dis[s] = 0;
  for (int i = 0; i < n; ++i) {
    int v = -1;
    for (int j = 0; j < n; ++j) {
      if (!vis[j] && (v == -1 || dis[j] < dis[v])) {
        v = j;
      }
    }

    // if (dis[v] == INF)... FAILED
    vis[v] = true;
    for (Edge e : adj[v]) {
      if (dis[v] + e.w < dis[e.to]) {
        dis[e.to] = dis[v] + e.w;
        prev[e.to] = v;
      }
    }
  }
}

void print_path() {
  vector<int> path;
  for (int v = t; v != s; v = p[v]) {
    path.push_back(v);
  }
  path.push_back(s);
  reverse(path.begin(), path.end());
  return path;
}

Dijkstra (Sparse, set/priority_queue, $O(m \lg n)$)

void dijkstra() {
  dis[s] = 0;
  set<pair<int, int>> q; // or priority_queue here
  q.insert({s, 0});
  while (!q.empty()) {
    int v = q.begin()->first;
    q.erase(q.begin());

    for (Edge e : adj[v]) {
      if (dis[v] + e.w < dis[e.to]) {
        q.erase({e.to, dis[e.to]});
        dis[e.to] = dis[v] + e.w;
        prev[e.to] = v;
        q.insert({e.to, d[e.to]});
      }
    }
  }
}

Bellman-Ford

void bellman_ford() {
  dis[s] = 0;
  while (true) { // change to i:0 to n-1 avoid negative cycle.
    bool any = false;
    for (int j = 0; j < m; ++j) {
      if (d[e[j].u] < INF) {
        if (d[e[j].u] + e[j].w < d[e[j].v]) {
          d[e[j].v] = d[e[j].u] + e[j].w;
          prev[e[j].v] = e[j].u;
          any = true;
        }
      }
      if (!any) break;
    }
  }
}

Floyd

void floyd() {
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (d[i][k] < INF && d[k][j] < INF) {
          d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
        //if (d[k][j] < INF && d[j][j] < 0 && d[j][i] < INF) {
        //  d[k][i] = -INF; // negative circle
        //}
      }
    }
    }
}

强连通分量

Kosaraju

void dfs1 (int v) {
  vis[v] = true;
  for (int i = 0; i < adj[v].size(); ++i) {
    if (!vis[adj[v][i]]) {
      dfs(adj[v][i]);
    }
  }
  order.push_back(v);
}

void dfs2(int v) {
  vis[v] = true;
  component.push_back(v);
  for (int i = 0; i < adj_rev[v].size(); ++i) {
    if (!vis[adj_rev[v][i]]) {
      dfs2(adj_rev[v][i]);
    }
  }
}

void kosaraju() {
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) dfs1(i);
  }
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i < n; ++i) {
    int v = order[n - 1 - i];
    if (!vis[v]) {
      dfs2(v);
      // ... save the component
      component.clear();
    }
  }
}

Tarjan's SCC Algorithm

for (int i = 0; i < n; ++i) {
  if (pre[i] == -1) tarjan(i);
}

void tarjan(int u) {
  pre[u] = low[u] = t++;
  s.push(u);
  inStack[u] = true;
  for (int j = 0; j < adj[u].size(); ++j) {
    int v = adj[u][j];
    if (pre[v] == -1) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (inStack[v]) {
      low[u] = min(low[u], pre[v]);
    }
  }
  if (pre[u] == low[u]) {
    int v;
    do {
      v = s.top();
      s.pop();
      inStack[v] = false;
      scc[v] = current_scc;
    } while (u != v);
    current_scc++;
  }
}

Tarjan 找割点/割边

经Massimo大佬指正修改了bug

-      if (low[v] >= pre[u] && u != 0) cut[v] = true;
+      if (low[v] >= pre[u] && u != 0) cut[u] = true;
void tarjan(int u) {
  pre[u] = low[u] = t++;
  for (int j = 0; j < adj[u].size(); ++j) {
    int v = adj[u][j];
    if (pre[v] == -1) {
      if (u == 0 && j >= 1) cut[u] = true;

      fa[v] = u;
      tarjan(v);
      low[u] = min(low[u], low[v]);

      if (low[v] >= pre[u] && u != 0) cut[u] = true;
      if (low[v] > pre[u]) bridge[u][v] = bridge[v][u] = true;
    } else if (v != fa[u]) {
      low[u] = min(low[u], pre[v]);
    }
  }
}

二分匹配

bool find (int u) {
  rep (v, 1, m + 1) {
    if (mp[u][v] && !vis[v]) {
      vis[v] = true;
      if (nex[v] < 0 || find(nex[v])) {
        nex[v] = u; // reverse residual edge
        return true;
      }
    }
  }
  return false;
}
int hungray() {
  int ret = 0;
  memset(nex, -1, sizeof(nex));
  rep (u, 1, n + 1) {
    memset(vis, 0, sizeof(vis));
    if (find(u)) ret++;
  }
  return ret;
}

欧拉回路 ($O(n)$)

void euler() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      deg[i] += adj[i][j];
    }
  }

  int first = 0;
  while (!deg[first]) first++;

  int v1 = -1, v2 = -1;
  bool bad = false;

  for (int i = 0; i < n; ++i) {
    if (deg[i] & 1) {
      if (v1 == -1) {
        v1 = i;
      } else if (v2 == -1) {
        v2 = i;
      } else {
        bad = true;
      }
    }
  }

  if (v1 != -1) {
    ++adj[v1][v2], ++adj[v2][v1];
  }

  stack<int> st;
  vector<int> res;
  st.push(first);
  while (!st.empty()) {
    int v = st.top();
    int i = 0;
    for (int i = 0; i < n; ++i) {
      if (adj[v][i]) break;
    }
    if (i == n) {
      res.push_back(v);
      st.pop();
    } else {
      --adj[v][i];
      --adj[i][v];
      st.push(i);
    }
  }

  if (v1 != -1) {
    for (int i = 0; i < res.size(); ++i) {
      if ((res[i] == v1 && res[i + 1] == v2) ||
          (res[i] == v2 && res[i + 1] == v1)) {
        vector<int> res2;
        for (int j = i + 1; j < res.size(); ++j) {
          res2.push_back(res[j]);
        }
        for (int j = 1; j <= i; ++j) {
          res2.push_back(res[j]);
        }
        res = res2;
        break;
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (adj[i][j]) bad = true;
    }
  }
  if (bad) {
    cout << -1;
  } else {
    for (int x : res) cout << x << " ";
  }
}

网络流

Dinic ($O(V^2E)$)

class FlowEdge {
 public:
  int u, v;
  int cap, flow = 0;
  FlowEdge(int u, int v, int cap)
      : u(u), v(v), cap(cap) {}
};

void addEdge(int u, int v, int cap) {
  edges.push_back({u, v, cap});
  edges.push_back({v, u, 0});
  adj[u].push_back(tot++);
  adj[v].push_back(tot++);
}

bool bfs() {
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int id : adj[u]) {
      FlowEdge e = edges[id];
      if (e.cap - e.flow < 1) continue;
      if (level[e.v] != -1) continue;
      level[e.v] = level[u] + 1;
      q.push(e.v);
    }
  }
  return level[t] != -1;
}

int dfs(int u, int pushed) {
  if (!pushed) return 0;
  if (u == t) return pushed;
  for (int &cid = ptr[u]; cid < adj[u].size(); ++cid) {
    int id = adj[u][cid];
    FlowEdge e = edges[id];
    int v = e.v;
    if (level[v] != level[u] + 1 || e.cap - e.flow < 1) continue;

    int delta = dfs(v, min(pushed, e.cap - e.flow));
    if (!delta) continue;

    edges[id].flow += delta;
    edges[id ^ 1].flow -= delta;
    return delta;
  }
  return 0;
}

int maxFlow() {
  int ret = 0;
  while (true) {
    memset(level, -1, sizeof(level));
    level[s] = 0;
    q.push(s);

    if (!bfs()) break;

    memset(ptr, 0, sizeof(ptr));
    while (true) {
      int pushed = dfs(s, INF);
      if (!pushed) break;
      ret += pushed;
    }
  }
  return ret;
}

发布于2019-01-07 23:04

学习