[关闭]
@Dmaxiya 2020-04-13T12:05:24.000000Z 字数 9433 阅读 1302

图论

板子


输出欧拉路径(HihoCoder 1181)

  1. const int maxn = 5000 + 100;
  2. // 欧拉路径输出从cnt – 1 到0输出u点下标,最后输出v点下标
  3. struct Node {
  4. int to;
  5. int Index;
  6. Node() {}
  7. Node(int t, int i) {
  8. to = t;
  9. Index = i;
  10. }
  11. };
  12. vector<Node> G[maxn];
  13. int deg[maxn];
  14. bool visit[maxn];
  15. int n, m, v, u;
  16. struct Edge {
  17. int u, v;
  18. Edge() {}
  19. Edge(int uu, int vv) {
  20. u = uu;
  21. v = vv;
  22. }
  23. };
  24. Edge e[maxn];
  25. int cnt;
  26. void dfs(int x) {
  27. int len = G[x].size();
  28. for(int i = 0; i < len; ++i) {
  29. int Index = G[x][i].Index;
  30. int pos = G[x][i].to;
  31. if(!visit[Index]) {
  32. visit[Index] = true;
  33. dfs(pos);
  34. e[cnt++] = Edge(x, pos);
  35. }
  36. }
  37. }
  38. for(int i = 0; i <= n; ++i) {
  39. if(deg[i] % 2 == 1) {
  40. u = i;
  41. break;
  42. }
  43. }
  44. dfs(u);
  45. for(int i = cnt - 1; i >= 0; --i) {
  46. printf("%d ", e[i].u);
  47. }
  48. printf("%d\n", e[0].v);

Tarjan 缩点(HDU 6165

  1. const int maxn = 1000 + 100;
  2. int top, bcnt, dcnt, n;
  3. int sta[maxn], dfn[maxn], low[maxn], belong[maxn];
  4. bool ins[maxn];
  5. vector<int> G[maxn];
  6. vector<int> GG[maxn];
  7. // G 为原图,GG 为缩点后的图
  8. // 缩点后的图总共有 bcnt 个点,下标范围为 [1, bcnt]
  9. // 若为无向图,dfs 时只需要多记录一个父节点
  10. // 使用时构好图到 G 中,直接调用 Tarjan 函数
  11. // belong[a] = b 表示原图上的节点 a 被缩至新图上的节点 b
  12. void dfs(int x) {
  13. dfn[x] = low[x] = ++dcnt;
  14. ins[x] = true;
  15. sta[top++] = x;
  16. int len = G[x].size();
  17. for(int i = 0; i < len; ++i) {
  18. int pos = G[x][i];
  19. if(dfn[pos] == 0) {
  20. dfs(pos);
  21. low[x] = min(low[x], low[pos]);
  22. } else if(ins[pos]) {
  23. low[x] = min(low[x], dfn[pos]);
  24. }
  25. }
  26. if(dfn[x] == low[x]) {
  27. ++bcnt;
  28. int pos;
  29. do {
  30. pos = sta[--top];
  31. ins[pos] = false;
  32. belong[pos] = bcnt;
  33. } while(pos != x);
  34. }
  35. }
  36. void Tarjan() {
  37. bcnt = top = dcnt = 0;
  38. memset(dfn + 1, 0, sizeof(int) * n);
  39. memset(ins + 1, 0, sizeof(bool) * n);
  40. for(int i = 1; i <= n; ++i) {
  41. if(dfn[i] == 0) {
  42. dfs(i);
  43. }
  44. }
  45. for(int i = 1; i <= bcnt; ++i) {
  46. GG[i].clear();
  47. }
  48. for(int i = 1; i <= n; ++i) {
  49. int len = G[i].size();
  50. for(int j = 0; j < len; ++j) {
  51. int pos = G[i][j];
  52. int u = belong[i];
  53. int v = belong[pos];
  54. if(u != v) {
  55. GG[u].push_back(v);
  56. }
  57. }
  58. }
  59. }

LCA/最近公共祖先

  1. const int Log = 20;
  2. const int maxn = 100000 + 100;
  3. int n, id_cnt;
  4. int fa[Log][maxn];
  5. vector<int> G[maxn];
  6. int id[maxn], depth[maxn];
  7. // 0 为树的虚根,depth[0] = 1,id[0] = 0
  8. // Log 等于树的层数取 log 的值,n 为树上点的数量,点下标从 1 开始
  9. void dfs(int f, int x, int d) {
  10. depth[x] = d;
  11. fa[0][x] = f;
  12. id[x] = ++id_cnt;
  13. int len = G[x].size();
  14. for(int i = 0; i < len; ++i) {
  15. int pos = G[x][i];
  16. if(pos != f) {
  17. dfs(x, pos, d + 1);
  18. }
  19. }
  20. }
  21. void prepare_skip_table() {
  22. id_cnt = 0;
  23. dfs(0, 1, 1);
  24. for(int j = 1; j < Log; ++j) {
  25. for(int i = 1; i <= n; ++i) {
  26. fa[j][i] = fa[j - 1][fa[j - 1][i]];
  27. }
  28. }
  29. }
  30. int Find(int x, int y) {
  31. if(x == y) {
  32. return x;
  33. }
  34. if(id[x] > id[y]) {
  35. swap(x, y);
  36. }
  37. for(int i = Log - 1; i >= 0; --i) {
  38. if(id[fa[i][y]] > id[x]) {
  39. y = fa[i][y];
  40. }
  41. }
  42. return fa[0][y];
  43. }

Dij

最短路

  1. const int maxn = 100 + 100;
  2. int dis[maxn];
  3. vector<Node> G[maxn];
  4. priority_queue<Node> que;
  5. // 优先队列为小顶堆,排序关键字为Node.dis,形参s 为起点下标
  6. void dij(int s) {
  7. memset(dis, 0x3f, sizeof(dis));
  8. dis[s] = 0;
  9. que.push(Node(s, 0));
  10. while(!que.empty()) {
  11. Node tmp = que.top();
  12. que.pop();
  13. int len = G[tmp.pos].size();
  14. for(int i = 0; i < len; ++i) {
  15. int pos = G[tmp.pos][i].pos;
  16. int d = G[tmp.pos][i].dis;
  17. if(dis[pos] > tmp.dis + d) {
  18. dis[pos] = tmp.dis + d;
  19. que.push(Node(pos, dis[pos]));
  20. }
  21. }
  22. }
  23. }

次短路(HDU 6181

  1. const int maxn = 100000 + 100;
  2. vector<Node> G[maxn];
  3. priority_queue<Node> que;
  4. int dis1[maxn], dis2[maxn];
  5. // 优先队列为小顶堆,排序关键字为Node.dis,形参s 为起点下标
  6. // dis1 为最短路,dis2 为次短路
  7. void dij(int s) {
  8. memset(dis1, 0x3f, sizeof(dis1));
  9. memset(dis2, 0x3f, sizeof(dis2));
  10. dis1[s] = 0;
  11. que.push(Node(s, 0));
  12. while(!que.empty()) {
  13. Node tmp = que.top();
  14. que.pop();
  15. int pos = tmp.pos;
  16. int dis = tmp.dis;
  17. if(dis2[pos] < dis) {
  18. continue;
  19. }
  20. int len = G[pos].size();
  21. for(int i = 0; i < len; ++i) {
  22. tmp = G[pos][i];
  23. int to = tmp.pos;
  24. int d2 = dis + tmp.dis;
  25. if(dis1[to] > d2) {
  26. swap(d2, dis1[to]);
  27. que.push(Node(to, dis1[to]));
  28. }
  29. if(dis2[to] > d2 && dis1[to] < d2) {
  30. dis2[to] = d2;
  31. que.push(Node(to, dis2[to]));
  32. }
  33. }
  34. }
  35. }

Spfa(HDU 3592

  1. const int maxn = 1000 + 100;
  2. const int INF = 0x3f3f3f3f;
  3. struct Node {
  4. int pos, dis;
  5. Node() {}
  6. Node(int p, int d) {
  7. pos = p;
  8. dis = d;
  9. }
  10. };
  11. int incnt[maxn], dis[maxn];
  12. bool inque[maxn];
  13. vector<Node> G[maxn];
  14. // maxn 为节点个数,下标从 1 开始
  15. // incnt 表示第 i 个节点入队的次数
  16. // dis 表示以 s 为起点的最短路
  17. // spfa 返回 false 表示有负环
  18. bool spfa(int s, int n) {
  19. memset(inque + 1, 0, sizeof(bool) * n);
  20. memset(dis + 1, 0x3f, sizeof(int) * n);
  21. memset(incnt + 1, 0, sizeof(int) * n);
  22. dis[s] = 0;
  23. inque[s] = true;
  24. incnt[s] = 1;
  25. queue<int> que;
  26. que.push(s);
  27. while(!que.empty()) {
  28. int tmp = que.front();
  29. que.pop();
  30. inque[tmp] = false;
  31. int len = G[tmp].size();
  32. for(int i = 0; i < len; ++i) {
  33. int pos = G[tmp][i].pos;
  34. int d = G[tmp][i].dis;
  35. if(dis[pos] > dis[tmp] + d) {
  36. dis[pos] = dis[tmp] + d;
  37. if(!inque[pos]) {
  38. inque[pos] = true;
  39. que.push(pos);
  40. if(++incnt[pos] > n) {
  41. return false;
  42. }
  43. }
  44. }
  45. }
  46. }
  47. return true;
  48. }

Prim 最小生成树

  1. const int maxn = 1000 + 100;
  2. int n;
  3. int pre[maxn];
  4. int ddis[maxn];
  5. int dis[maxn][maxn];
  6. bool visit[maxn];
  7. queue<int> que;
  8. vector<int> G[maxn];
  9. // n 为图上节点数量,pre表示节点i与生成树距离最短连边的节点
  10. // ddis表示节点i到最小生成树的距离,dis为完全图上任意两点间距离
  11. // visit表示是否在最小生成树上,G为最小生成树
  12. void Prim() {
  13. memset(visit, 0, sizeof(visit));
  14. memset(ddis, 0x3f, sizeof(ddis));
  15. for(int i = 1; i <= n; ++i) {
  16. G[i].clear();
  17. }
  18. que.push(1);
  19. while(!que.empty()) {
  20. int tmp = que.front();
  21. que.pop();
  22. ddis[tmp] = 0;
  23. visit[tmp] = true;
  24. int Min = INT_MAX;
  25. int pos = -1;
  26. for(int i = 1; i <= n; ++i) {
  27. if(!visit[i]) {
  28. if(ddis[i] > dis[tmp][i]) {
  29. ddis[i] = dis[tmp][i];
  30. pre[i] = tmp;
  31. }
  32. }
  33. }
  34. for(int i = 1; i <= n; ++i) {
  35. if(!visit[i] && Min > ddis[i]) {
  36. Min = ddis[i];
  37. pos = i;
  38. }
  39. }
  40. if(pos != -1) {
  41. tmp = pre[pos];
  42. que.push(pos);
  43. G[tmp].push_back(pos);
  44. G[pos].push_back(tmp);
  45. }
  46. }
  47. }

并查集

  1. const int maxn = 1000 + 100;
  2. int fa[maxn];
  3. // 节点下标范围为[from, to]
  4. inline void init(int from, int to) {
  5. For(i, from, to) fa[i] = i;
  6. }
  7. int Find(int x) {
  8. return ((x == fa[x])? x: (fa[x] = Find(fa[x])));
  9. }
  10. void unit(int x, int y) {
  11. int xx = Find(x);
  12. int yy = Find(y);
  13. fa[xx] = yy;
  14. }

二分图匹配

无权二分图最大匹配 Hopcroft-Carp(HDU 2389

  1. const int maxn = 3001;
  2. int Nx, Ny;
  3. int dx[maxn], dy[maxn];
  4. int Mx[maxn], My[maxn];
  5. vector<int> G[maxn];
  6. bool vis[maxn];
  7. // 使用时需设好 Nx Ny 和 G,G 中只需要存下从 Nx 到 Ny 所有节点的边,不需要从 Ny 到 Nx 的边
  8. // 时间复杂度 O(sqrt(n)*m),n 为节点数,m为边数
  9. // Nx, Ny 分别表示左右两边节点数量,编号从 1 开始
  10. // 最终匹配结果存在 Mx 与 My 中
  11. // Mx[a] = b 表示左边的 a 与右边的 b 匹配,同时 My[b] = a
  12. // 直接调用 hopcroft_karp 函数返回最大匹配数量
  13. bool Find(int x) {
  14. int len = G[x].size();
  15. for(int i = 0; i < len; ++i) {
  16. int pos = G[x][i];
  17. if(!vis[pos] && dy[pos] == dx[x] + 1) {
  18. vis[pos] = true;
  19. if(My[pos] == 0 || Find(My[pos])) {
  20. My[pos] = x;
  21. Mx[x] = pos;
  22. return true;
  23. }
  24. }
  25. }
  26. return false;
  27. }
  28. int hopcroft_karp() {
  29. int ret = 0;
  30. memset(Mx + 1, 0, sizeof(int) * Nx);
  31. memset(My + 1, 0, sizeof(int) * Ny);
  32. bool flag = true;
  33. while(flag) {
  34. flag = false;
  35. queue<int> que;
  36. for(int i = 1; i <= Nx; ++i) {
  37. if(Mx[i] == 0) {
  38. que.push(i);
  39. }
  40. }
  41. memset(dx + 1, 0, sizeof(int) * Nx);
  42. memset(dy + 1, 0, sizeof(int) * Ny);
  43. memset(vis + 1, 0, sizeof(bool) * Ny);
  44. while(!que.empty()) {
  45. int x = que.front();
  46. que.pop();
  47. int len = G[x].size();
  48. for(int i = 0; i < len; ++i) {
  49. int pos = G[x][i];
  50. if(dy[pos] == 0) {
  51. dy[pos] = dx[x] + 1;
  52. if(My[pos] != 0) {
  53. dx[My[pos]] = dy[pos] + 1;
  54. que.push(My[pos]);
  55. } else {
  56. flag = true;
  57. }
  58. }
  59. }
  60. }
  61. if(!flag) {
  62. break;
  63. }
  64. for(int i = 1; i <= Nx; ++i) {
  65. if(!Mx[i] && Find(i)) {
  66. ++ret;
  67. }
  68. }
  69. }
  70. return ret;
  71. }

带权二分图最大权匹配 KM(HDU 2255

  1. const int maxn = 301;
  2. const LL INF = 1e18;
  3. int n;
  4. LL G[maxn][maxn];
  5. LL lx[maxn], ly[maxn], slack[maxn];
  6. int My[maxn], Mx[maxn];
  7. int pre[maxn];
  8. bool visy[maxn];
  9. // 使用时需设好 n 和 G,下标从 1 开始
  10. // 时间复杂度 O(n^3),n 为节点数
  11. // 最终匹配结果存在 Mx 与 My 中
  12. // Mx[a] = b 表示左边的 a 与右边的 b 匹配,同时 My[b] = a
  13. // 直接调用 KM 函数返回最大匹配权值
  14. // 求最小权匹配可将权值取相反数
  15. void augment(int root) {
  16. fill(visy + 1, visy + n + 1, false);
  17. fill(slack + 1, slack + n + 1, INF);
  18. int py;
  19. My[py = 0] = root;
  20. do {
  21. visy[py] = true;
  22. int x = My[py], yy;
  23. LL delta = INF;
  24. for(int y = 1; y <= n; y++) {
  25. if(!visy[y]) {
  26. if(lx[x] + ly[y] - G[x][y] < slack[y]) {
  27. slack[y] = lx[x] + ly[y] - G[x][y];
  28. pre[y] = py;
  29. }
  30. if(slack[y] < delta) {
  31. delta = slack[y];
  32. yy = y;
  33. }
  34. }
  35. }
  36. for(int y = 0; y <= n; y++) {
  37. if(visy[y]) {
  38. lx[My[y]] -= delta;
  39. ly[y] += delta;
  40. } else {
  41. slack[y] -= delta;
  42. }
  43. }
  44. py = yy;
  45. } while(My[py] != -1);
  46. do {
  47. int Pre = pre[py];
  48. My[py] = My[Pre];
  49. py = Pre;
  50. } while(py != 0);
  51. }
  52. LL KM() {
  53. for(int i = 1; i <= n; i++) {
  54. lx[i] = ly[i] = 0;
  55. My[i] = -1;
  56. for(int j = 1; j <= n; j++) {
  57. lx[i] = max(lx[i], G[i][j]);
  58. }
  59. }
  60. LL answer = 0;
  61. for(int root = 1; root <= n; root++) {
  62. augment(root);
  63. }
  64. for(int i = 1; i <= n; ++i) {
  65. Mx[My[i]] = i;
  66. }
  67. for(int i = 1; i <= n; i++) {
  68. answer += lx[i];
  69. answer += ly[i];
  70. }
  71. return answer;
  72. }

网络流(POJ 1273

  1. const int maxn = 200 + 100;
  2. const int maxm = 200 + 100;
  3. const int INF = 0x3f3f3f3f;
  4. // 时间复杂度为 O(n^2 * m),n 为节点数量,m 为边数
  5. // maxm 为需要加边的数量,即调用 addEdge 的总次数
  6. // 使用前需调用 Init 初始化
  7. struct Edge {
  8. int to, Next, flow, cap;
  9. Edge() {}
  10. Edge(int t, int n, int f, int c) {
  11. to = t;
  12. Next = n;
  13. flow = f;
  14. cap = c;
  15. }
  16. };
  17. int N, S, T, ecnt;
  18. int head[maxn], cur[maxn], d[maxn];
  19. Edge edge[maxm << 1];
  20. // 节点总个数,节点编号从 0 ~ N - 1
  21. void Init(int n) {
  22. N = n;
  23. ecnt = 0;
  24. memset(head, -1, sizeof(int) * N);
  25. }
  26. void addEdge(int u, int v, int c) {
  27. edge[ecnt] = Edge(v, head[u], 0, c);
  28. head[u] = ecnt++;
  29. edge[ecnt] = Edge(u, head[v], 0, 0);
  30. head[v] = ecnt++;
  31. }
  32. void add_s_t() {
  33. // 将源点和汇点连入图中
  34. }
  35. bool bfs() {
  36. queue<int> que;
  37. for(int i = 0; i < N; ++i) {
  38. d[i] = 0;
  39. }
  40. que.push(S);
  41. d[S] = 1;
  42. while(!que.empty()) {
  43. int tmp = que.front();
  44. que.pop();
  45. for(int id = head[tmp]; id != -1; id = edge[id].Next) {
  46. if(d[edge[id].to] == 0 && edge[id].cap > edge[id].flow) {
  47. d[edge[id].to] = d[tmp] + 1;
  48. que.push(edge[id].to);
  49. }
  50. }
  51. }
  52. return d[T] != 0;
  53. }
  54. int dfs(int x, int res) {
  55. if(x == T || res == 0) {
  56. return res;
  57. }
  58. int ret = 0, tmp;
  59. for(int &id = cur[x]; id != -1; id = edge[id].Next) {
  60. int pos = edge[id].to;
  61. if(d[pos] == d[x] + 1 && edge[id].cap > edge[id].flow) {
  62. tmp = dfs(pos, min(res, edge[id].cap - edge[id].flow));
  63. if(tmp > 0) {
  64. ret += tmp;
  65. res -= tmp;
  66. edge[id].flow += tmp;
  67. edge[id ^ 1].flow -= tmp;
  68. if(res == 0) {
  69. break;
  70. }
  71. }
  72. }
  73. }
  74. return ret;
  75. }
  76. // 调用 Dinic 前需构好图
  77. // 直接调用函数返回 maxflow
  78. int Dinic(int s, int t) {
  79. int flow = 0;
  80. S = s;
  81. T = t;
  82. add_s_t();
  83. while(bfs()) {
  84. for(int i = 0; i < N; ++i) {
  85. cur[i] = head[i];
  86. }
  87. flow += dfs(S, INF);
  88. }
  89. return flow;
  90. }

最小费用最大流(POJ 2135

  1. const int maxn = 1000 + 100;
  2. const int maxm = 20000 + 100;
  3. const int INF = 0x3f3f3f3f;
  4. // 时间复杂度为流量 * 边数 * 常数(2)
  5. // 求最大费用只需要将费用取相反数
  6. // maxm 为需要加边的数量,即调用 addEdge 的总次数
  7. // 使用前需调用 Init 初始化
  8. struct Edge {
  9. int to, Next, cap, flow, cost;
  10. Edge() {}
  11. Edge(int t, int n, int ca, int f, int co) {
  12. to = t;
  13. Next = n;
  14. cap = ca;
  15. flow = f;
  16. cost = co;
  17. }
  18. };
  19. int N;
  20. int head[maxn], ecnt;
  21. int pre[maxn], dis[maxn];
  22. bool inque[maxn];
  23. Edge edge[maxm << 1];
  24. // 节点总个数,节点编号从 0 ~ N - 1
  25. void Init(int n) {
  26. N = n;
  27. ecnt = 0;
  28. memset(head, -1, sizeof(int) * N);
  29. }
  30. void addEdge(int u, int v, int cap, int cost) {
  31. edge[ecnt] = Edge(v, head[u], cap, 0, cost);
  32. head[u] = ecnt++;
  33. edge[ecnt] = Edge(u, head[v], 0, 0, -cost);
  34. head[v] = ecnt++;
  35. }
  36. void add_s_t() {
  37. // 将源点和汇点连入图中
  38. }
  39. bool spfa(int s, int t) {
  40. queue<int> que;
  41. for(int i = 0; i < N; i++) {
  42. dis[i] = INF;
  43. inque[i] = false;
  44. pre[i] = -1;
  45. }
  46. dis[s] = 0;
  47. inque[s] = true;
  48. que.push(s);
  49. while(!que.empty()) {
  50. int u = que.front();
  51. que.pop();
  52. inque[u] = false;
  53. for(int i = head[u]; i != -1; i = edge[i].Next) {
  54. int v = edge[i].to;
  55. if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
  56. dis[v] = dis[u] + edge[i].cost;
  57. pre[v] = i;
  58. if(!inque[v]) {
  59. inque[v] = true;
  60. que.push(v);
  61. }
  62. }
  63. }
  64. }
  65. return pre[t] != -1;
  66. }
  67. // 调用 minCostMaxflow 前需构好图
  68. // 返回的是 maxflow,cost存的是最小费用
  69. int minCostMaxflow(int s, int t, int &cost) {
  70. int flow = 0;
  71. cost = 0;
  72. add_s_t();
  73. while(spfa(s,t)) {
  74. int Min = INF;
  75. for(int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) {
  76. if(Min > edge[i].cap - edge[i].flow) {
  77. Min = edge[i].cap - edge[i].flow;
  78. }
  79. }
  80. for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) {
  81. edge[i].flow += Min;
  82. edge[i ^ 1].flow -= Min;
  83. cost += edge[i].cost * Min;
  84. }
  85. flow += Min;
  86. }
  87. return flow;
  88. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注