有参加蓝桥杯的同学可以给博主点个关注，博主也在准备蓝桥杯，可以跟着博主的博客一起刷题。

蓝桥杯

我的AcWing

题目及图片来自蓝桥杯C++ AB组辅导课

图论

蓝桥杯省赛中的图论都是很简单的图论。

第七届2016年蓝桥杯真题

AcWing 1224. 交换瓶子

JavaA组第9题

图论+环+置换群

这个题直接想是比较麻烦的，我们转换成图论的方式去思考，把每一个瓶子看成一个点，每个点连到自己应该在的位置，如图：

瓶子3连位置3，此时位置3是瓶子2，瓶子2连位置2，此时位置2是瓶子1，3 2 1成环；瓶子4连位置4，此时位置4是瓶子5，瓶子5连瓶子4，此时4 5成环。

n个点，n条边，出度是1，入度也是1。

我们最终希望它变成五个自环：

题中一次只能交换两个数，我们看看交换两个数会在图中产生怎样的影响：

① 情况1：交换同一个环内的点 => 必然会裂成两个环，交换3和1：

瓶子1指向位置1，也就是指向自己，瓶子2指向位置2，也就是指向瓶子3。

② 情况2：交换不同环中的点 => 必然会合并两个环。

假设有k个环，最终想变成n个环，每一次操作最多只能增加1个环，我们最少需要n - k次操作才可以把n个环变成k个环。

我们发现这个题转换成图来考虑就变得很清晰了。

图论解法

时间复杂度 $O(N)$

import java.util.Scanner;public class Main {    static final int N = 10010;    static int[] b = new int[N];    static boolean[] st = new boolean[N]; // 判重数组 记录是否有环    public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 1; i <= n; i++) b[i] = sc.nextInt();  int cnt = 0; for (int i = 1; i <= n; i++) {     if (!st[i]) {  cnt++;  for (int j = i; !st[j]; j = b[j]) { // 位置j指向b[j]的元素      st[j] = true;  }     } } System.out.print(n - cnt);    }}

暴力枚举

时间复杂度 O ( N 2 ) O(N^2) O(N2)

暴力思路可以参考这个人的题解。

import java.util.Scanner;public class Main {    static final int N = 10010;    static int[] b = new int[N];    public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 1; i <= n; i++) b[i] = sc.nextInt();  int cnt = 0; for (int i = 1; i <= n; i++) {     if (b[i] != i) {  for (int j = i + 1; j <= n; j++) {      if (b[j] == i) {   int t = b[i];   b[i] = b[j];   b[j] = t;      }  }  cnt++;     } } System.out.print(cnt);    }}

第四届2013年蓝桥杯真题

AcWing 1207. 大臣的旅费

JavaA组第10题

从某一点到到其它所有点的路径都是唯一的，说明无环，无环连通图就是一棵树。

走1千米花费11，走2千米要花费23：

假设走了 $S$ 千米远，总花费为：$10+1+10+2+10+3+......+10+s$，整理得： f ( s ) = 10 ⋅ s + s⋅(s+1) 2 f(s) = 10⋅s + \frac{s ⋅ (s + 1)}{ 2} f(s)=10⋅s+2s⋅(s+1)​

函数是单调递增的，所以s越大函数值越大。

这个题本质就是给我们一棵树，让我们求这棵树中长度最长的一条路径，也就是找树的直径。

为什么上图距离y最大值就是直径呢？我们证明一下：

情况1：直径与当前路径有交点：假设一个直径vu与xy相交与o点：

首先y是距离x最远的一个点之一，因此xu一定小于等于xy，这两条路径有公共部分xo，将公共部分去掉得：：$oy⩾ou$，所以$vy⩾vu$，因为vu是直径，所以vy必然也是直径，所以y必然是某一直径的起点。

情况2：直径与当前路径没有交点：uv是一条直径

因为树中任意两点之间都会有一条唯一的路径，所以pq就作为连通两点的路径。

由于y是到x最远的一个距离，所以$xy⩾xv$，也就是，$py⩾pv$ 所以一定 $py⩾qv$，，$qy⩾qv$，推出 $uy⩾uv$，所以uy也肯定是一条直径，所以y必然是某一直径的起点。

写一个函数，求出所有点到某一个点的距离，我们可以用dfs实现。

y总分享：

图一般有两种存储方式：

1. 邻接矩阵。开个二维数组，g[i][j] 表示点 i 和点 j 之间的边权。
2. 邻接表。邻接表有两种常用写法，我推荐第二种，代码更简洁，效率也更高，后面有代码模板：
   (1) 二维List：List<List> edge，edge[i][j] 表示第 i 个点的第 j 条邻边。
   (2) 数组模拟邻接表：为每个点开个单链表，分别存储该点的所有邻边。

本题用邻接表的集合存储。

import java.util.Scanner;import java.util.List;import java.util.ArrayList;public class Main {    static final int N = 100010;    static int n;    static List[] list = new ArrayList[N]; // vertor    static int[] dist = new int[N]; // 距离    public static void main(String[] args) { for(int i = 0; i < N; i++) list[i] = new ArrayList<Edge>(); Scanner sc = new Scanner(System.in); n = sc.nextInt(); for (int i = 0; i < n - 1; i++) {     int a = sc.nextInt();     int b = sc.nextInt();     int c = sc.nextInt();     list[a].add(new Edge(b, c));     list[b].add(new Edge(a, c)); } dfs(1, -1, 0); // 找到距离任意点x最远的点y int u = 1; for (int i = 1; i <= n; i++) {     if (dist[i] > dist[u]) {  u = i;     } } dfs(u, -1, 0); // 找到距离点y最远的点 即是树的直径 for (int i = 1; i <= n; i++) {     if (dist[i] > dist[u]) {  u = i;     } } long s = dist[u]; System.out.println((10 * s + s * (s + 1) / 2)); // 推导的公式    }    private static void dfs(int u, int father, int distance) { dist[u] = distance; // 遍历当前节点的所有节点 for (Object temp : list[u]) {     Edge node = (Edge)temp;     if (node.id != father) {  dfs(node.id, u, distance + node.w);     } }    }    static class Edge { int id; int w; public Edge(int id, int w) {     this.id = id;     this.w = w; }    }}

有对代码不理解的地方可以在下方评论