转载自: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