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