图论专题整理

主要是将各种算法简单整理了一下，对于算法的具体原理没有过于深入的讲解。

最小生成树（MST）：

给定一个n个节点的连通图，它的生成树就是原图的一个子图，它包含了原图的n个点和n-1条边。

最小生成树就是权值和最小的生成树。

kruskal算法求最小生成树：

1. 将原图的边按权值由小到大排序。
2. 依次考虑所有的边i，如果i的两端点u，v还没有连通，则将i加入最小生成树并将u，v标记为连通，否则抛弃i。

节点的连通性用并查集来维护。

代码模板：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define MAXV 1000
#define MAXE 4000

using namespace std;

struct Edge {
    int u;
    int v;
    int value;
    Edge() {}
    Edge(int a, int b, int c) : u(a), v(b), value(c) {}
    bool operator < (const Edge &e) const {
        return value < e.value;
    }
};

int V, E;
int parent[MAXV]; // 并查集
Edge edges[MAXE];
vector<Edge> ans;

int find(int p) {
    if (parent[p] == p) return p;
    return parent[p] = find(parent[p]);
}

void un(int p, int q) {
    parent[find(p)] = find(q);
}

int main() {
    scanf("%d %d", &V, &E);
    int x, y, z;
    for (int i = 0; i < E; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].value);
    }
    sort(edges, edges + E);
    for (int i = 0; i < V; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < E; i++) {
        Edge e = edges[i];
        if (find(e.u) != find(e.v)) {
            ans.push_back(e);
            un(e.u, e.v);
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        printf("%d %d %d\n", ans[i].u, ans[i].v, ans[i].value);
    }
    return 0;
}

练习：

• poj1251 Jungle Roads 【解题报告】

• CodeForces 472D Design Tutorial: Inverse the Problem 【解题报告】

• poj1789 Truck History 【解题报告】

• poj1639 Picnic Planning
  （顶点度数限制的MST） 【解题报告】

最短路：

单源的SPFA算法：

spfa可以求从源点s到其他所有点的最短路。
spfa可以处理有负权的边，但是不能处理负环。

流程：
记从源点s到点v的最短路为dist[v]，
dist数组初始为无穷大，dist[s]=0。
vis数组表示点是否在队列中

1. 将源点入队，vis[s]=1

2. 依次取队首元素u，考虑u连接的所有节点v
   如果dist[u] + w[u][v] < dist[v]，则更新dist[v] = dist[u] + w[u][v]，如果vis[v]==false则将v入队。

3. 在可能有负环的题目中，还要用一个cnt数组记录每个点的入队次数，如果某个点入队次数大于节点总数n，则说明有负环。

代码模板（邻接表）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cstdio>

#define MAXV 1000000
#define INF 0x3f3f3f3f

using namespace std;

struct Edge {
    int v;  // 边权
    int to; // 连接的点
    Edge() {}
    Edge(int a, int b) : v(a), to(b) {}
};

vector<Edge> edges[MAXV];
int V;
int E;
int dist[MAXV];
int vis[MAXV];
int cnt[MAXV];
queue<int> q;

bool spfa(int s) {
    while (!q.empty()) q.pop();
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    q.push(s);
    dist[s] = 0;
    vis[s] = 1;
    cnt[s] = 1;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = 0; i < edges[current].size(); i++) {
            Edge e = edges[current][i];
            if (dist[current] + e.v < dist[e.to]) {
                dist[e.to] = dist[current] + e.v;
                if (!vis[e.to]) {
                    vis[e.to] = 1;
                    cnt[e.to]++;
                    if (cnt[e.to] > V) return false;
                }
            }
        }
        vis[current] = false; // current已经出队
    }
    return true;
}

int main( void ) {
    scanf("%d %d", &V, &E);
    int i, x, y, l;
    for (int i = 0; i < E; i++) {
        scanf("%d%d%d", &x, &y, &l);
        edges[x].push_back(Edge(y, l)); //将这条边压入x的表中
    }
    if(!spfa(0)){ //出现负环
        printf("no answer\n");
    }else{ //存在最短路
        printf("Node 0 to node %d : %d", V-1, dist[V-1]);
    }
    return 0;
}

spfa算法的复杂度是O(k|E|)，k是一个常数，一般为2或3

任意两点最短路的floyd算法：

floyd算法可以在O(n3)的时间里计算出任意两点之间的最短路。
原理很好理解，直接贴关键部分代码：

for (int k = 1; k <= n; k++) // 注意k一定在最外层循环
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

练习：

• poj1062 昂贵的聘礼 【解题报告】

• poj1847 Tram 【解题报告】

• poj1797 Heavy Transportation
  SPFA变形 【解题报告】

• poj1724 ROADS
  SPFA+A* 【解题报告】

• poj1125 Stockbroker Grapevine
  floyd 【解题报告】

• poj1275 Cashier Employment
  差分约束 【解题报告】

• poj1716 Integer Intervals
  差分约束 【解题报告】

二分图匹配：

二分图：如果无向图G=(V, E)的顶点集V可以分成两个不相交的子集A和B，
且G中的每一条边的两个端点（u，v）分别在两个子集中（u∈A，v∈B），则称G为二分图。

二分图的性质：

最小点覆盖=最大匹配数
最小路径覆盖=总节点数-最大匹配数
最大独立集=顶点数-最大匹配数

最大匹配的匈牙利算法：

最大匹配：给定一个二分图G，M是G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

图中包含边数最多的匹配称为图的最大匹配。

匈牙利算法：

就是不断dfs寻找增广路，并增加匹配个数。

增广路是一条“交错路径”，即起点和终点都是未匹配点，而路径经过的边是未匹配-匹配-未匹配这样交替出现。

可见，增广路有奇数条边，未匹配边比匹配边多一条。此时将所有未匹配边变为匹配边，匹配边变为未匹配边，匹配仍然成立，而匹配数+1。

代码模板：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define MAXV 100

using namespace std;

int V, E; // 二分图的每一侧各V个节点，节点编号1~V
vector<int> edges[MAXV];
int mat[MAXV]; // mat[i] = j：与右侧节点i匹配的左侧节点为j
int vis[MAXV];

bool dfs(int k) { // k为左侧的节点
    for (int i = 0; i < edges[k].size(); i++) {
        int j = edges[k][i];
        if (!vis[j]) {
            vis[j] = 1;
            if (!mat[j] || dfs(mat[j])) {
                mat[j] = k;
                return true;
            }
        }
    }
    return false;
}

int match() {
    int ans = 0;
    for (int i = 1; i <= V; i++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) ans++;
    }
    return ans;
}

int main() {
    scanf("%d %d", &V, &E);
    int a, b;
    for (int i = 0; i < E; i++) {
        scanf("%d %d", &a, &b);
        edges[a].push_back(b);
    }
    int ans = match();
    printf("%d\n", ans);
    return 0;
}

练习：

• poj1325 Machine Schedule
  最小点覆盖 【解题报告】

• poj3041 Asteroids
  最小点覆盖 【解题报告】

• poj2060 Taxi Cab Scheme
  最小路径覆盖 【解题报告】

• poj1466 Girls and Boys
  最大独立集 【解题报告】

• poj1486 Sorting Slides
  二分图匹配的必须边 【解题报告】

带权值的二分图匹配的KM算法：

如果给定的二分图是带权值的，并且要求匹配的权值和最大（最小），就要用到KM算法。

代码模板（最小权值匹配，注释中的是最大权值匹配）：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

#define INF 0x7fffffff

using namespace std;

int n, m;
int cntA, cntB;
int edges[100][100];
int A[100], B[100];
bool visA[100], visB[100];
int mat[100];
int d;

bool dfs(int i) {
    visA[i] = 1;
    for (int j = 1; j <= n * m; j++) {
        if (!visB[j]) {
            int t = edges[i][j] - A[i] - B[j];
            if (!t) {
                visB[j] = 1;
                if (!mat[j] || dfs(mat[j])) {
                    mat[j] = i;
                    return true;
                }
            } else d = min(d, t);
        }
    }
    return false;
}

int match() {
    memset(B, 0, sizeof(B));
    for (int i = 1; i <= n; i++) {
        A[i] = INF; // A[i] = -INF;
        for (int j = 1; j <= m; j++)
            A[i] = min(A[i], edges[i][j]); // A[i] = max(A[i], edges[i][j])
    }
    memset(mat, 0, sizeof(mat));
    for (int i = 1; i <= n; i++) {
        while (true) {
            memset(visA, 0, sizeof(visA));
            memset(visB, 0, sizeof(visB));
            d = INF;
            if (dfs(i)) break;
            for (int j = 1; j <= n; j++)
                if (visA[j]) A[j] += d;  //A[j] -= d;
            for (int j = 1; j <= m; j++)
                if (visB[j]) B[j] -= d;  //A[j] += d;
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans += edges[mat[i]][i];
    return ans;
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d %d", &n, &m);
        int t;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &edges[i][j]);
            }
        }
        int ans = match();
        printf("%d\n", ans);
    }
    return 0;
}

练习：

• poj2195 Going Home
  最小权值匹配 【解题报告】

• poj2516 Minimum Cost
  拆点+最小权值匹配 【解题报告】

• poj3686 The Windy’s
  最小权值匹配 【解题报告】

网络流：

最大流的dinic算法：

先介绍层次图的概念：

层次图，就是把原图中的点按照点到源的距离分“层”，只保留不同层之间的边的图。

算法流程：

1. 根据残量网络计算层次图。
2. 在层次图中使用DFS进行增广直到不存在增广路。
3. 重复以上步骤直到无法增广。

代码模板：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXV = 10000;

/**
    储存弧的结构
    代表从from到to，容量为cap， 流量为flow
*/
struct Edge{
    int from, to, cap, flow;
};

int V, E, S, T;
vector<Edge> edges; // 边 edges[e]和edges[e ^ 1]互为反向弧
vector<int> G[MAXV]; // 邻接表 G[i][j]表示节点i的第j条边在edges中的序号
bool vis[MAXV];     // build方法中使用，表示的i条边有没有被标号过
int layer[MAXV];    // 节点i的层
int cur[MAXV];      // 当前弧下标

/**
    插入弧
    将插入两条弧，一条是它本身，一条是它的反向弧
    edges[i]与edges[i ^ 1]互为反向弧
*/
void addEdge(int from, int to, int cap) {
    Edge temp;
    temp.from = from;
    temp.to = to;
    temp.cap = cap;
    temp.flow = 0;
    edges.push_back(temp);
    temp.from = to;
    temp.to = from;
    temp.cap = 0;
    temp.flow = 0;
    edges.push_back(temp);
    E = edges.size();
    G[from].push_back(E - 2);
    G[to].push_back(E - 1);
}

/**
    建立层次图
    @return：是否存在s-t路径
*/
bool build() {
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(S);
    layer[S] = 0;
    vis[S] = 1;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < G[x].size(); i++) {
            Edge& e = edges[G[x][i]];
            if (!vis[e.to] && e.cap > e.flow) { // 只考虑残量网络中的弧
                vis[e.to] = 1;
                layer[e.to] = layer[x] + 1;
                q.push(e.to);
            }
        }
    }
    return vis[T];
}

/**
    寻找增广路
    @param x：当前节点
    @param a：目前为止所有弧的最小残量
    @return：流量
*/
int find(int x, int a) {
    if (x == T || a == 0) return a;
    int flow = 0;
    int f;
    for (int& i = cur[x]; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (layer[x] + 1 == layer[e.to]
            && (f = find(e.to, min(a, e.cap - e.flow))) != 0) {
            e.flow += f;
            edges[G[x][i] ^ 1].flow -= f;
            flow += f;
            a -= f;
            if (!a)
                break;
        }
    }
    return flow;
}

int dinic(int s, int t) {
    S = s;
    T = t;
    int flow = 0;
    while(build()) {
        memset(cur, 0, sizeof(cur));
        flow += find(s, INF);
    }
    return flow;
}

int main( void ) {
    scanf("%d %d", &V, &E);
    int e = E;
    int x, y, l;
    for (int i = 0; i < e; i++) {
        scanf("%d %d %d", &x, &y, &l);
        addEdge(x, y, l);
    }
    printf("%d\n", dinic(1, V));
    return 0;
}

练习：

• poj1087 A Plug for UNIX
  思路：最大流 【解题报告】

• poj1459 Power Network
  思路：最大流 【解题报告】

• poj2391 Ombrophobic Bovines
  思路：二分+拆点+网络流 【解题报告】

• poj2455 Secret Milking Machine
  思路：二分+网络流 【解题报告】

• poj2987 Firing
  思路：最大权闭合图 【解题报告】

• NOI2006 最大获利
  思路：最大权闭合图 【解题报告】

最小费用最大流：

如果网络中的每条边都有一个花费，在保证流量最大时，还要求花费最少，这就是最小费用最大流（费用流）问题。

代码模板：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

#define MAXV 1000
#define INF 0x3f3f3f3f

using namespace std;

struct Edge{
    int from, to, cap, flow, cost;
    Edge(int u, int v, int c, int f, int x)
        : from(u), to(v), cap(c), flow(f), cost(x) {}
};

int V, E;
vector<int> G[MAXV];
vector<Edge> edges;
bool done[MAXV];
int dist[MAXV];
int previous[MAXV]; // previous[i]表示顶点i的前一条弧在edges的索引
int a[MAXV];    // a[i]表示当前顶点i的可改进流量

void addEdge(int from, int to, int cap, int cost) {
    edges.push_back(Edge(from, to, cap, 0, cost));
    edges.push_back(Edge(to, from, 0, 0, -cost));
    E = edges.size();
    G[from].push_back(E - 2);
    G[to].push_back(E - 1);
}

bool spfa(int s, int t, int& flow, int& cost) {
    for (int i = 0; i <= V; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;
    memset(done, 0, sizeof(done));
    done[s] = 1;
    previous[s] = 0;
    a[s] = INF;
    queue<int> buff;
    buff.push(s);
    while(!buff.empty()) {
        int current = buff.front();
        buff.pop();
        done[current] = 0;
        for (int i = 0; i < G[current].size(); i++) {
            Edge& e = edges[G[current][i]];
            if (e.cap > e.flow && dist[e.to] > dist[current] + e.cost) {
                dist[e.to] = dist[current] + e.cost;
                previous[e.to] = G[current][i];
                a[e.to] = min(a[current], e.cap - e.flow);
                if (!done[e.to]) {
                    done[e.to] = 1;
                    buff.push(e.to);
                }
            }
        }
    }
    if (dist[t] == INF)
        return false;
    flow += a[t];
    cost += dist[t] * a[t];
    for (int u = t; u != s; u = edges[previous[u]].from) {
        edges[previous[u]].flow += a[t];
        edges[previous[u] ^ 1].flow -= a[t];
    }
    return true;
}

int minCostMaxFlow(int s, int t) {
    int flow = 0;
    int cost = 0;
    while(spfa(s, t, flow, cost));
    return cost;
}

int main( void ) {
    scanf("%d %d", &V, &E);
    int e = E;
    int u, v, c, cost;
    for (int i = 0; i < e; i++) {
        scanf("%d %d %d %d", &u, &v, &c, &cost);
        addEdge(u, v, c, cost);
    }
    printf("%d\n", minCostMaxFlow(1, V));
    return 0;
}

练习：

• poj3422 Kaka’s Matrix Travels
  思路：拆点+费用流 【解题报告】

• spoj371 Boxes
  思路：费用流 【解题报告】

强连通分量：

强连通分量：

• 有向图G中，如果两个顶点u, v间有一条从u到v的有向路径，同时还有一条从v到u的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。

• 简单来说就是G’是G的一个子图，对于G’中的所有点V’，两两互相可以到达，就说G’是G的一个强连通分量。

Tarjan算法：

1. 对图进行dfs，将遍历到的节点压入栈中。
2. 设dfn[u]为节点u的搜索的次序编号，low[u]为节点u或u的子树能够追溯到的最早的栈中节点的次序号。
3. 当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。此时依次弹出栈中元素直到v=u。

代码模板：

int dfs(int u) {
    stack.push(u);
    vis[u] = 1;
    ++cnt;
    low[u] = dfn[u] = cnt;
    for (int j = 0; j < lin[u].size(); j++) {
        int v = lin[u][j];
        if (!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        int t;
        num++;
        do {
            t = stack.top();
            col[t] = num;
            stack.pop();
            vis[t] = 0;
        }
        while (t != u);
    }
}

练习：

• poj1904 King’s Quest
  强连通分量 【解题报告】

• poj2553 The Bottom of a Graph
  强连通分量 【解题报告】

• poj2186 Popular Cows
  强连通分量 【解题报告】

• poj2762 Going from u to v or from v to u?
  强连通分量+dp找最长链 【解题报告】

• poj2723 Get Luffy Out
  二分+2-SAT 【解题报告】

• poj3207 Ikki’s Story IV - Panda’s Trick
  2-SAT 【解题报告】

• poj3905 Perfect Election
  2-SAT 【解题报告】