图论相关算法

236


转载自:http://cojs.tk/cogs/page/page.php?aid=30


  • 最小生成树
    • Kruskal+ufs
      int ufs(int x){
          return f[x] == x ? x : f[x] = ufs(f[x]); 
      } 
      int Kruskal(int n,int m) {
          int w = 0;
          for(int i = 0; i < n; i++)
              f[i] = i;
          sort(e,e + m);
          for(int i = 0; i < m; 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
      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); 
      }
      ```
      
  • 网络流
    • 费用流:Bellman-Ford 找增广路,或者用贪心求解
    • 最大流:Edmonds-KarpS
发布评论
  • 点击查看/关闭被识别为广告的评论