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

图论

板子

输出欧拉路径(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;
  27. void dfs(int x) {
  28.     int len = G[x].size();
  29.     for(int i = 0; i < len; ++i) {
  30.         int Index = G[x][i].Index;
  31.         int pos = G[x][i].to;
  32.         if(!visit[Index]) {
  33.             visit[Index] = true;
  34.             dfs(pos);
  35.             e[cnt++] = Edge(x, pos);
  36.         }
  37.     }
  38. }
  40. for(int i = 0; i <= n; ++i) {
  41.     if(deg[i] % 2 == 1) {
  42.         u = i;
  43.         break;
  44.     }
  45. }
  46. dfs(u);
  47. for(int i = cnt - 1; i >= 0; --i) {
  48.     printf("%d ", e[i].u);
  49. }
  50. 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. }
  37. void Tarjan() {
  38.     bcnt = top = dcnt = 0;
  39.     memset(dfn + 1, 0, sizeof(int) * n);
  40.     memset(ins + 1, 0, sizeof(bool) * n);
  41.     for(int i = 1; i <= n; ++i) {
  42.         if(dfn[i] == 0) {
  43.             dfs(i);
  44.         }
  45.     }
  46.     for(int i = 1; i <= bcnt; ++i) {
  47.         GG[i].clear();
  48.     }
  49.     for(int i = 1; i <= n; ++i) {
  50.         int len = G[i].size();
  51.         for(int j = 0; j < len; ++j) {
  52.             int pos = G[i][j];
  53.             int u = belong[i];
  54.             int v = belong[pos];
  55.             if(u != v) {
  56.                 GG[u].push_back(v);
  57.             }
  58.         }
  59.     }
  60. }

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. }
  22. void prepare_skip_table() {
  23.     id_cnt = 0;
  24.     dfs(0, 1, 1);
  25.     for(int j = 1; j < Log; ++j) {
  26.         for(int i = 1; i <= n; ++i) {
  27.             fa[j][i] = fa[j - 1][fa[j - 1][i]];
  28.         }
  29.     }
  30. }
  32. int Find(int x, int y) {
  33.     if(x == y) {
  34.         return x;
  35.     }
  36.     if(id[x] > id[y]) {
  37.         swap(x, y);
  38.     }
  39.     for(int i = Log - 1; i >= 0; --i) {
  40.         if(id[fa[i][y]] > id[x]) {
  41.             y = fa[i][y];
  42.         }
  43.     }
  44.     return fa[0][y];
  45. }

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

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. }
  8. int Find(int x) {
  9.     return ((x == fa[x])? x: (fa[x] = Find(fa[x])));
  10. }
  12. void unit(int x, int y) {
  13.     int xx = Find(x);
  14.     int yy = Find(y);
  15.     fa[xx] = yy;
  16. }

二分图匹配

无权二分图最大匹配 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. }
  29. int hopcroft_karp() {
  30.     int ret = 0;
  31.     memset(Mx + 1, 0, sizeof(int) * Nx);
  32.     memset(My + 1, 0, sizeof(int) * Ny);
  33.     bool flag = true;
  34.     while(flag) {
  35.         flag = false;
  36.         queue<int> que;
  37.         for(int i = 1; i <= Nx; ++i) {
  38.             if(Mx[i] == 0) {
  39.                 que.push(i);
  40.             }
  41.         }
  42.         memset(dx + 1, 0, sizeof(int) * Nx);
  43.         memset(dy + 1, 0, sizeof(int) * Ny);
  44.         memset(vis + 1, 0, sizeof(bool) * Ny);
  45.         while(!que.empty()) {
  46.             int x = que.front();
  47.             que.pop();
  48.             int len = G[x].size();
  49.             for(int i = 0; i < len; ++i) {
  50.                 int pos = G[x][i];
  51.                 if(dy[pos] == 0) {
  52.                     dy[pos] = dx[x] + 1;
  53.                     if(My[pos] != 0) {
  54.                         dx[My[pos]] = dy[pos] + 1;
  55.                         que.push(My[pos]);
  56.                     } else {
  57.                         flag = true;
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.         if(!flag) {
  63.             break;
  64.         }
  65.         for(int i = 1; i <= Nx; ++i) {
  66.             if(!Mx[i] && Find(i)) {
  67.                 ++ret;
  68.             }
  69.         }
  70.     }
  71.     return ret;
  72. }

带权二分图最大权匹配 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. }
  53. LL KM() {
  54.     for(int i = 1; i <= n; i++) {
  55.         lx[i] = ly[i] = 0;
  56.         My[i] = -1;
  57.         for(int j = 1; j <= n; j++) {
  58.             lx[i] = max(lx[i], G[i][j]);
  59.         }
  60.     }
  61.     LL answer = 0;
  62.     for(int root = 1; root <= n; root++) {
  63.         augment(root);
  64.     }
  65.     for(int i = 1; i <= n; ++i) {
  66.         Mx[My[i]] = i;
  67.     }
  68.     for(int i = 1; i <= n; i++) {
  69.         answer += lx[i];
  70.         answer += ly[i];
  71.     }
  72.     return answer;
  73. }

网络流（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. };
  18. int N, S, T, ecnt;
  19. int head[maxn], cur[maxn], d[maxn];
  20. Edge edge[maxm << 1];
  21. // 节点总个数，节点编号从 0 ~ N - 1
  22. void Init(int n) {
  23.     N = n;
  24.     ecnt = 0;
  25.     memset(head, -1, sizeof(int) * N);
  26. }
  28. void addEdge(int u, int v, int c) {
  29.     edge[ecnt] = Edge(v, head[u], 0, c);
  30.     head[u] = ecnt++;
  31.     edge[ecnt] = Edge(u, head[v], 0, 0);
  32.     head[v] = ecnt++;
  33. }
  35. void add_s_t() {
  36.     // 将源点和汇点连入图中
  37. }
  39. bool bfs() {
  40.     queue<int> que;
  41.     for(int i = 0; i < N; ++i) {
  42.         d[i] = 0;
  43.     }
  44.     que.push(S);
  45.     d[S] = 1;
  46.     while(!que.empty()) {
  47.         int tmp = que.front();
  48.         que.pop();
  49.         for(int id = head[tmp]; id != -1; id = edge[id].Next) {
  50.             if(d[edge[id].to] == 0 && edge[id].cap > edge[id].flow) {
  51.                 d[edge[id].to] = d[tmp] + 1;
  52.                 que.push(edge[id].to);
  53.             }
  54.         }
  55.     }
  56.     return d[T] != 0;
  57. }
  59. int dfs(int x, int res) {
  60.     if(x == T || res == 0) {
  61.         return res;
  62.     }
  63.     int ret = 0, tmp;
  64.     for(int &id = cur[x]; id != -1; id = edge[id].Next) {
  65.         int pos = edge[id].to;
  66.         if(d[pos] == d[x] + 1 && edge[id].cap > edge[id].flow) {
  67.             tmp = dfs(pos, min(res, edge[id].cap - edge[id].flow));
  68.             if(tmp > 0) {
  69.                 ret += tmp;
  70.                 res -= tmp;
  71.                 edge[id].flow += tmp;
  72.                 edge[id ^ 1].flow -= tmp;
  73.                 if(res == 0) {
  74.                     break;
  75.                 }
  76.             }
  77.         }
  78.     }
  79.     return ret;
  80. }
  81. // 调用 Dinic 前需构好图
  82. // 直接调用函数返回 maxflow
  83. int Dinic(int s, int t) {
  84.     int flow = 0;
  85.     S = s;
  86.     T = t;
  87.     add_s_t();
  88.     while(bfs()) {
  89.         for(int i = 0; i < N; ++i) {
  90.             cur[i] = head[i];
  91.         }
  92.         flow += dfs(S, INF);
  93.     }
  94.     return flow;
  95. }

最小费用最大流（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. };
  20. int N;
  21. int head[maxn], ecnt;
  22. int pre[maxn], dis[maxn];
  23. bool inque[maxn];
  24. Edge edge[maxm << 1];
  25. // 节点总个数，节点编号从 0 ~ N - 1
  26. void Init(int n) {
  27.     N = n;
  28.     ecnt = 0;
  29.     memset(head, -1, sizeof(int) * N);
  30. }
  32. void addEdge(int u, int v, int cap, int cost) {
  33.     edge[ecnt] = Edge(v, head[u], cap, 0, cost);
  34.     head[u] = ecnt++;
  35.     edge[ecnt] = Edge(u, head[v], 0, 0, -cost);
  36.     head[v] = ecnt++;
  37. }
  39. void add_s_t() {
  40.     // 将源点和汇点连入图中
  41. }
  43. bool spfa(int s, int t) {
  44.     queue<int> que;
  45.     for(int i = 0; i < N; i++) {
  46.         dis[i] = INF;
  47.         inque[i] = false;
  48.         pre[i] = -1;
  49.     }
  50.     dis[s] = 0;
  51.     inque[s] = true;
  52.     que.push(s);
  53.     while(!que.empty()) {
  54.         int u = que.front();
  55.         que.pop();
  56.         inque[u] = false;
  57.         for(int i = head[u]; i != -1; i = edge[i].Next) {
  58.             int v = edge[i].to;
  59.             if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
  60.                 dis[v] = dis[u] + edge[i].cost;
  61.                 pre[v] = i;
  62.                 if(!inque[v]) {
  63.                     inque[v] = true;
  64.                     que.push(v);
  65.                 }
  66.             }
  67.         }
  68.     }
  69.     return pre[t] != -1;
  70. }
  71. // 调用 minCostMaxflow 前需构好图
  72. // 返回的是 maxflow，cost存的是最小费用
  73. int minCostMaxflow(int s, int t, int &cost) {
  74.     int flow = 0;
  75.     cost = 0;
  76.     add_s_t();
  77.     while(spfa(s,t)) {
  78.         int Min = INF;
  79.         for(int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) {
  80.             if(Min > edge[i].cap - edge[i].flow) {
  81.                 Min = edge[i].cap - edge[i].flow;
  82.             }
  83.         }
  84.         for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]) {
  85.             edge[i].flow += Min;
  86.             edge[i ^ 1].flow -= Min;
  87.             cost += edge[i].cost * Min;
  88.         }
  89.         flow += Min;
  90.     }
  91.     return flow;
  92. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注