图论专题整理专题整理

主要是将各种算法简单整理了一下，对于算法的具体原理没有过于深入的讲解。
最小生成树（MST）：
给定一个n个节点的连通图，它的生成树就是原图的一个子图，它包含了原图的n个点和n-1条边。
最小生成树就是权值和最小的生成树。
kruskal算法求最小生成树：

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

节点的连通性用并查集来维护。
代码模板：

#include #include #include #include #define MAXV 1000 #define MAXE 4000using 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 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数组表示点是否在队列中

将源点入队，vis[s]=1
依次取队首元素u，考虑u连接的所有节点v
如果dist[u] + w[u][v] < dist[v]，则更新dist[v] = dist[u] + w[u][v]，如果vis[v]==false则将v入队。
在可能有负环的题目中，还要用一个cnt数组记录每个点的入队次数，如果某个点入队次数大于节点总数n，则说明有负环。

代码模板（邻接表）：

#include #include #include #include #include #include #define MAXV 1000000 #define INF 0x3f3f3f3fusing namespace std; struct Edge { int v; // 边权 int to; // 连接的点 Edge() {} Edge(int a, int b) : v(a), to(b) {} }; vector edges[MAXV]; int V; int E; int dist[MAXV]; int vis[MAXV]; int cnt[MAXV]; queue 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 #include #include #include #define MAXV 100using namespace std; int V, E; // 二分图的每一侧各V个节点，节点编号1~V vector 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 #include #include #include #define INF 0x7fffffffusing 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 <= 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; //B[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算法：先介绍层次图的概念： 层次图，就是把原图中的点按照点到源的距离分“层”，只保留不同层之间的边的图。
算法流程：

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

代码模板：

#include #include #include #include #include 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 edges; // 边 edges[e]和edges[e ^ 1]互为反向弧 vector 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 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 #include #include #include #include #define MAXV 1000 #define INF 0x3f3f3f3fusing 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 G[MAXV]; vector 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 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算法：

对图进行dfs，将遍历到的节点压入栈中。
设dfn[u]为节点u的搜索的次序编号，low[u]为节点u或u的子树能够追溯到的最早的栈中节点的次序号。
当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); } }

练习：