图论入门

First Post:

2024-03-11

Last Update:

2024-03-31

图论

本章节为图论最基本的内容，要求每位同学都要尽量掌握。

图的基本概念

图：由点(node，或者 vertex)和连接点的边(edge)组成。图是点和边构成的网。

树：特殊的图

树，即连通无环图树的结点从根开始，层层扩展子树，是一种层次关系，这种层次关系，保证了树上不会出现环路。两点之间的路径：有且仅有一条路径。最近公共祖先。

图的种类

（1）无向无权图，边没有权值、没有方向；（2）有向无权图，边有方向、无权值；（3）加权无向图，边有权值，但没有方向；（4）加权有向图；（5）有向无环图（Directed Acyclic Graph，DAG）。

图算法的时间分析

图算法的复杂度和边的数量 E、点的数量 V 相关。$O(V+E)$：几乎是图问题中能达到的最好程度。$O(V\log E)$、$O(E\log V)$：很好的算法。$O(V^2)$、$O(E^2)$或更高：不算是好的算法。

图的存储

能快速访问：图的存储，能让程序很快定位结点 u 和 v 的边(u, v) 。

数组存边：简单、空间使用最少；无法快递定位
邻接矩阵：简单、空间使用最大；定位最快 dis[a][b]
邻接表：空间很少，定位较快
链式前向星：空间更少，定位较快

注：存储方式跟题目相匹配，占用空间少定位快也不一定是问题的最优存储方式。

数组存边

优点：简单、最省空间。缺点：无法定位某条边。应用：bellman-ford 算法、最小生成树的 kruskal 算法

// c/c++实现
struct Edge{
    int from,to,dis;
}e[M]; //结构体数组存边

cin>>n>>m;

for(int i=1;i<=m;++i)
    cin>>e[i].from>>e[i].to>>e[i].dis;

Java

//Java实现
class Edge { int from; int to; int dis;

    public Edge(int from, int to, int dis) {
        this.from = from;
        this.to = to;
        this.dis = dis;
    }

}

Edge[] e = new Edge[M];

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();

for (int i = 0; i < m; ++i)
{
    int from = sc.nextInt();
    int to = sc.nextInt();
    int dis = sc.nextInt();
    e[i] = new Edge(from, to, dis);
}

Python

#python实现
class Edge:
    def init(self, f, t, d):
        self.from = f
        self.to = t
        self.dis = d

e = [Edge(0, 0, 0) for i in range(M)]

n, m = map(int, input().split())

for i in range(1, m + 1):
    e[i].from, e[i].to, e[i].dis = map(int, input().split())

邻接矩阵

二维数组： $graph[NUM ][NUM ]$ 无向图： $graph[i][j]=graph[j][i]。$ 有向图： $graph[i][j]\neq graph[j][i]。$ 权值： $graph[i][j]存结点i到j的边的权值。$ 例如 $graph[1][2]= 3，graph[2][1] = 5等等。$ 用 $graph[i][j]= INF表示i，j之间无边。$

优点：

适合稠密图；
编码非常简短；
对边的存储、查询、更新等操作又快又简单。

缺点：

存储复杂度 $O(V^2)$太高。V=10000 时，空间 100M。
不能存储重边。

邻接表和链式前向星

邻接表（指针或数组下标）和链式前向星（容器模拟）的思路一样，只是表达方式不同。

图片描述

struct edge{
    int from, to; long long w; //起点，终点，权值。起点from并没有用到，e[i]的i就是from
    edge(int a, int b,long long c){from=a; to=b; w=c;}
};
vector<edge>e[N];          //用于存储图

Java

static class Edge {
    int from, to;
    long w;

    Edge(int a, int b, long c) {
        from = a;
        to = b;
        w = c;
    }
}
static ArrayList<Edge>[] e = new ArrayList[N];

Python

class Edge:
    def __init__(self, fr, to, w):
        self.fr = fr
        self.to = to
        self.w = w

e = [[] for _ in range(N)]

我们会在使用的时候进行讲解。

最短路问题

最广为人知的图论问题就是最短路径问题。

简单图的最短路径

树上的路径：任意 $2$ 点之间

只有一条路径

所有边长都为 $1$ 的图：用 BFS 搜最短路径，复杂度 $O(n+m)$

普通图的最短路径

边长：不一定等于 $1$，而且可能为负数
算法：Floyd、Dijkstra、SPFA 等，各有应用场景，不可互相替代

最短路算法比较

问题	边权	算法	时间复杂度
一个起点，一个终点	非负数；无边权（或边权为 1）	A*	< $O((m+n)\log n)$
		双向广搜	< $O((m+n)\log n)$
		贪心最优搜索	< $O(m+n)$
一个起点到其他所有点	无边权（或边权为 1）	BFS	$O(m+n)$
	非负数	Dijkstra(堆优化优先队列)	$O((m+n)\log n)$
	允许有负数	SPFA	< $O(mn)$
所有点对之间	允许有负数	Floyd-Warshall	$O(n^3)$

什么算法也不能解决存在负环图的最短路的问题！最多是判断是否存在，或者找到负环。

网站推荐：CSAcademy Graph Editor

图片描述

方便图论的学习。

Floyd 算法

最简单的最短路径算法，代码仅有 $4$ 行
存图：最简单的矩阵存图
易懂，比暴力的搜索更简单易懂。
效率不高，不能用于大图在某些场景下有自己的优势，难以替代。能做传递闭包问题（离散数学）

C++、Java

//java 和 c++
for(int k=1; k<=n; k++)         //floyd的三重循环
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)      // k循环在i、j循环外面
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

Python

#python
for k in range(1, n+1): #floyd的三重循环
    for i in range(1, n+1):
        for j in range(1, n+1): # k循环在i、j循环外面
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

Floyd算法：多源最短路算法，一次计算能得到图中每一对结点之间（多对多）的最短路径。 Dijkstra、Bellman-Ford、SPFA算法：单源最短路径算法（Single source shortest path algorithm），一次计算能得到一个起点到其他所有点（一对多）的最短路径。在截止目前的蓝桥杯大赛中，Floyd算法是最常见的最短路径算法。以上统计包括国赛和省赛，所以另外两种仍然要进行学习。

Floyd 算法思想：动态规划

下面为 Floyd 算法的原理，不看背代码也可以。

动态规划：求图上两点 i、j 之间的最短距离，按“从小图到全图”的步骤，在逐步扩大图的过程中计算和更新最短路。
定义状态：dp[k][i][j]，i、j、k是点的编号，范围 1 ~ n。状态dp[k][i][j]表示在包含 1 ~ k 点的子图上，点对 i、j 之间的最短路。
状态转移方程：从子图 1 ~ k-1 扩展到子图 1 ~ k $dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])$

首先是包含 1 ~ k-1 点的子图。 $dp[k-1][i][j]$：不包含 k 点子图内的点对 i、j 的最短路； $dp[k-1][i][k] + dp[k-1][k][j]$：经过 k 点的新路径的长度，即这条路径从 i 出发，先到 k，再从 k 到终点 j。比较：不经过 k 的最短路径$dp[k-1][i][j]$和经过 k 的新路径，较小者就是新的$dp[k][i][j]$。

所以 Floyd 的原理就是每次引入一个新的点，用它去更新其他点的最短距离。

k 从 1 逐步扩展到 n：最后得到的$dp[n][i][j]$是点对 i、j 之间的最短路径长度。初值$dp[0][i][j]$：若 i、j 是直连的，就是它们的边长；若不直连，赋值为无穷大。 i、j 是任意点对：计算结束后得到了所有点对之间的最短路。

$dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])$ 用滚动数组简化： $dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])$

特点：

在一次计算后求得所有结点之间的最短距离。
代码极其简单，是最简单的最短路算法。
效率低下，计算复杂度是 $O(n^3)$，只能用于 $n < 300$ 的小规模的图。
存图用邻接矩阵 dp[][] 。因为 Floyd 算法计算的结果是所有点对之间的最短路，本身就需要 n^2 的空间，用矩阵存储最合适。
能判断负圈。负圈：若图中有权值为负的边，某个经过这个负边的环路，所有边长相加的总长度也是负数，这就是负圈。在这个负圈上每绕一圈，总长度就更小，从而陷入在负圈上兜圈子的死循环。 Floyd 算法很容易判断负圈，只要在算法运行过程出现任意一个 dp[i][i] < 0 就说明有负圈。因为 dp[i][i] 是从 i 出发，经过其他中转点绕一圈回到自己的最短路径，如果小于零，就存在负圈。

Dijkstra 算法

Dijkstra：单源最短路径问题。
优点：非常高效而且稳定。
缺点：只能处理不含有负权边的图。
思路：贪心思想+优先队列。

算法思想

Dijkstra 算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

为什么是每次都是找最小的？

因为最小边的不会被其它的点松弛，只有可能最小边去松弛别人。如果存在一个点 $K$ 能够松弛 $ab$ 的话那么一定有 $ak$ 距离加上 $kb$ 的距离小于 $ab$，已知 $ab$ 最短，所以不存在 $ak + kb < ab$。

Dijkstra 算法应用了贪心法的思想，即“抄近路走，肯定能找到最短路径”。

算法高效稳定：

Dijkstra 的每次迭代，只需要检查上次已经确定最短路径的那些结点的邻居，检查范围很小，算法是高效的；
每次迭代，都能得到至少一个结点的最短路径，算法是稳定的

优先队列实现：

每次往队列中放新数据时，按从小到大的顺序放，采用小顶堆的方式，复杂度是 $O(logn)$，保证最小的数总在最前面；
找最小值，直接取 B 的第一个数，复杂度是 $O(1)$。
复杂度：用优先队列时，Dijkstra 算法的复杂度是 $O(mlogn)$，是最高效的最短路算法。

维护两个集合：已确定最短路径的结点集合 A、这些结点向外扩散的邻居结点集合 B。

把起点 s 放到 A 中，把 s 所有的邻居放到 B 中。此时，邻居到 s 的距离就是直连距离。
从 B 中找出距离起点 s 最短的结点 u，放到 A 中。
把 u 所有的新邻居放到 B 中。显然，u 的每一条边都连接了一个邻居，每个新邻居都要加进去。其中 u 的一个新邻居 v，它到 s 的距离 dis(s, v) 等于 dis(s, u) + dis(u, v)。
重复(2)、(3)，直到 B 为空时，结束。

Dijkstra 的局限性是边的权值不能为负数：

Dijkstra 基于 BFS，计算过程是从起点 s 逐步往外扩散的过程，每扩散一次就用贪心得到到一个点的最短路。扩散要求路径越来越长，如果遇到一个负权边，会导致路径变短，使扩散失效。

Dijkstra 模板如下：

#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
//这样定义INF的好处是: INF <= INF+x
const int N= 3e5+2;
struct edge{
    int from, to; long long w; //起点，终点，权值。起点from并没有用到，e[i]的i就是from
    edge(int a, int b,long long c){from=a; to=b; w=c;}
};
vector<edge>e[N];          //用于存储图
struct s_node{
    int id; long long n_dis;   //id：结点；n_dis：这个结点到起点的距离
    s_node(int b,long long c){id=b; n_dis=c;}
    bool operator < (const s_node & a) const
    { return n_dis > a.n_dis;}
};
int n,m;
int pre[N];                                //记录前驱结点，用于生成路径
void print_path(int s, int t) {            //打印从s到t的最短路
    if(s==t){ printf("%d ", s); return; }  //打印起点
    print_path(s, pre[t]);                 //先打印前一个点
    printf("%d ", t);                      //后打印当前点。最后打印的是终点t
}
long long  dis[N];         //记录所有结点到起点的距离
void dijkstra(){
    int s = 1;             //起点s是1
    bool done[N]; //done[i]=true表示到结点i的最短路径已经找到
    for (int i=1;i<=n;i++) {dis[i]=INF; done[i]=false; }    //初始化
    dis[s]=0;                           //起点到自己的距离是0
    priority_queue <s_node> Q;          //优先队列，存结点信息
    Q.push(s_node(s, dis[s]));          //起点进队列
    while (!Q.empty())   {
        s_node u = Q.top();             //pop出距起点s距离最小的结点u
        Q.pop();
        if(done[u.id])  continue;       //丢弃已经找到最短路径的结点。即集合A中的结点            
        done[u.id]= true;
        for (int i=0; i<e[u.id].size(); i++) {  //检查结点u的所有邻居
            edge y = e[u.id][i];         //u.id的第i个邻居是y.to
            if(done[y.to])  continue;    //丢弃已经找到最短路径的邻居结点                
            if (dis[y.to] > y.w + u.n_dis) {
                dis[y.to] = y.w + u.n_dis;
                Q.push(s_node(y.to, dis[y.to]));  //扩展新的邻居，放到优先队列中
                pre[y.to]=u.id;  //如果有需要，记录路径
            }
        }
    }
    // print_path(s,n);          //如果有需要，打印路径: 起点1，终点n
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)    e[i].clear();
    while (m--) {
        int u,v,w;  scanf("%d%d%lld",&u,&v,&w);
        e[u].push_back(edge(u,v,w));
     // e[v].push_back(edge(v,u,w));    //本题是单向道路
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(dis[i]>=INF)  cout<<"-1 ";
        else   printf("%lld ", dis[i]);
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static final long INF = 0x3f3f3f3f3f3f3f3fL;
    static final int N = 300005;
    static ArrayList<Edge>[] e = new ArrayList[N];
    static int n, m;
    static int[] pre = new int[N];
    static long[] dis = new long[N];
    static boolean[] done = new boolean[N];

    static class Edge {
        int from, to;
        long w;

        Edge(int a, int b, long c) {
            from = a;
            to = b;
            w = c;
        }
    }

    static class SNode implements Comparable<SNode> {
        int id;
        long n_dis;

        SNode(int b, long c) {
            id = b;
            n_dis = c;
        }

        public int compareTo(SNode o) {
            return Long.compare(n_dis, o.n_dis);
        }
    }

    static void printPath(int s, int t) {
        if (s == t) {
            System.out.print(s + " ");
            return;
        }
        printPath(s, pre[t]);
        System.out.print(t + " ");
    }

    static void dijkstra() {
        int s = 1;
        PriorityQueue<SNode> Q = new PriorityQueue<>();
        Arrays.fill(dis, INF);
        dis[s] = 0;
        Q.offer(new SNode(s, dis[s]));
        while (!Q.isEmpty()) {
            SNode u = Q.poll();
            if (done[u.id])
                continue;
            done[u.id] = true;
            for (Edge y : e[u.id]) {
                if (done[y.to])
                    continue;
                if (dis[y.to] > y.w + u.n_dis) {
                    dis[y.to] = y.w + u.n_dis;
                    Q.offer(new SNode(y.to, dis[y.to]));
                    pre[y.to] = u.id;
                }
            }
        }
        // printPath(s, n);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= n; i++)
            e[i] = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            long w = Long.parseLong(st.nextToken());
            e[u].add(new Edge(u, v, w));
            // e[v].add(new Edge(v, u, w)); //本题是单向道路
        }
        dijkstra();
        for (int i = 1; i <= n; i++) {
            if (dis[i] >= INF)
                System.out.print("-1 ");
            else
                System.out.print(dis[i] + " ");
        }
    }
}

Python

import heapq

INF = 0x3f3f3f3f3f3f3f3f
N = 300002

class Edge:
    def __init__(self, fr, to, w):
        self.fr = fr
        self.to = to
        self.w = w

class SNode:
    def __init__(self, id, n_dis):
        self.id = id
        self.n_dis = n_dis

    def __lt__(self, other):
        return self.n_dis < other.n_dis

def print_path(s, t):
    if s == t:
        print(s, end=" ")
        return
    print_path(s, pre[t])
    print(t, end=" ")

def dijkstra():
    s = 1
    done = [False] * N
    dis = [INF] * N
    pre = [-1] * N
    dis[s] = 0
    pq = []
    heapq.heappush(pq, SNode(s, dis[s]))
    while pq:
        u = heapq.heappop(pq)
        if done[u.id]:
            continue
        done[u.id] = True
        for y in e[u.id]:
            if done[y.to]:
                continue
            if dis[y.to] > y.w + u.n_dis:
                dis[y.to] = y.w + u.n_dis
                heapq.heappush(pq, SNode(y.to, dis[y.to]))
                pre[y.to] = u.id
    for i in range(1, n+1):
        if dis[i] >= INF:
            print("-1", end=" ")
        else:
            print(dis[i], end=" ")

n, m = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(m):
    u, v, w = map(int, input().split())
    e[u].append(Edge(u, v, w))

dijkstra()

Bellman-Ford 算法

BFS 的扩散思想，每个人都去问自己的相邻节点到 S 点的距离最近是多少。

第一轮至少有一个点得到了到 S 的最短距离，即与 S 相邻的节点，标记为 T1

重复以上操作，那么必然至少又有一个节点找到了与 S 的最短距离，即与 T1 相邻的节点，标记为 T2

一共需要几轮操作？

每一轮操作，都至少有一个新的结点得到了到 S 的最短路径。所以，最多只需要 n 轮操作，就能完成 n 个结点。在每一轮操作中，需要检查所有 m 个边，更新最短距离。

Bellman-Ford 算法的复杂度：O(nm)。

Bellman-Ford 能判断负圈：

没有负圈时，只需要 n 轮就结束。

如果超过 n 轮，最短路径还有变化，那么肯定有负圈。

SPFA 算法

队列优化版的 Bellman-Ford

SPFA = 队列处理+Bellman-Ford。

Bellman-Ford 算法有很多低效或无效的操作。其核心内容，是在每一轮操作中，更新所有结点到起点 S 的最短距离。计算和调整一个结点 U 到 S 的最短距离后，如果紧接着调整 U 的邻居结点，这些邻居肯定有新的计算结果；而如果漫无目的地计算不与 U 相邻的结点，很可能毫无变化，所以这些操作是低效的。

改进： 计算结点 U 之后，下一步只计算和调整它的邻居，能加快收敛的过程。这些步骤用队列进行操作，这就是 SPFA。

（1）起点 S 入队，计算它所有邻居到 S 的最短距离。把 S 出队，状态有更新的邻居入队，没更新的不入队。（2）现在队列的头部是 S 的一个邻居 U。弹出 U，更新它所有邻居的状态，把其中有状态变化的邻居入队列。（3）继续以上过程，直到队列空。这也意味着，所有结点的状态都不再更新。最后的状态就是到起点 S 的最短路径。

弹出 U 之后，在后面的计算中，U 可能会再次更新状态（后来发现，U 借道别的结点去 S，路更近）。所以，U 可能需要重新入队列。有可能只有很少结点重新进入队列，也有可能很多。这取决于图的特征。

所以，SPFA 是不稳定的,所以根据题目的类型，我们要选择合适的算法。

SPFA 模板如下：

#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3+10;
struct edge{
    int to;    long long w;
    edge(int tt,long long ww) {to = tt; w = ww;}
};
long long dist[N];
int inq[N];
vector<edge> e[N];
void spfa(int s){
    memset(dist,0x3f,sizeof(dist));
    dist[s] = 0;      //起点到自己的距离是0
    queue<int> q;
    q.push(s);        //从s开始，s进队列
    inq[s] = 1;       //起点在队列中
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;   //u已经不在队列中
        if(dist[u] == INF)     continue;
        for(int i = 0;i < e[u].size();i++) {   //遍历u的邻居
            int v = e[u][i].to;
            long long w = e[u][i].w;
            if(dist[v] > dist[u]+w) {         //u的第i个邻居v，它借道u，到s更近
                dist[v] = dist[u]+w;          //更新邻居v到s的距离
                if(!inq[v]) {      //邻居v更新状态了，但v不在队列中，放进队列
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
}
int main(){
    int n,m,s;cin>>n>>m>>s;
    for(int i = 1;i <= m;i++)    {
        int u,v; long long w;
        cin>>u>>v>>w;
        e[u].push_back(edge(v,w));
    }
    spfa(s);
    for(int i = 1;i <= n;i++) {
        if(dist[i]==INF)  cout << -1;
        else              cout << dist[i];
        if(i != n)        cout << " ";
        else              cout << endl;
    }
    return 0;
}

Java

import java.util.*;

public class Main {
    static final long INF = 0x3f3f3f3f3f3f3f3fL;
    static final int N = 5010;

    static long[] dist = new long[N];
    static int[] inq = new int[N];
    static List<edge>[] e = new ArrayList[N];

    static class edge {
        int to;
        long w;

        public edge(int tt, long ww) {
            to = tt;
            w = ww;
        }
    }

    static void spfa(int s) {
        Arrays.fill(dist, INF);
        dist[s] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        inq[s] = 1;
        while (!q.isEmpty()) {
            int u = q.poll();
            inq[u] = 0;
            if (dist[u] == INF) continue;
            for (int i = 0; i < e[u].size(); i++) {
                int v = e[u].get(i).to;
                long w = e[u].get(i).w;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    if (inq[v] == 0) {
                        q.add(v);
                        inq[v] = 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int s = in.nextInt();
        for (int i = 1; i <= n; i++) {
            e[i] = new ArrayList<>();
        }
        for (int i = 1; i <= m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            long w = in.nextLong();
            e[u].add(new edge(v, w));
        }
        spfa(s);
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) System.out.print("-1 ");
            else System.out.print(dist[i] + " ");
        }
    }
}

Python

import heapq

INF = 0x3f3f3f3f3f3f3f3f
N = 5010

class Edge:
    def __init__(self, to, w):
        self.to = to
        self.w = w

dist = [INF] * N
inq = [0] * N
e = [[] for _ in range(N)]

def spfa(s):
    global dist
    global inq
    dist = [INF] * N
    dist[s] = 0
    q = []
    heapq.heappush(q, s)
    inq[s] = 1
    while q:
        u = heapq.heappop(q)
        inq[u] = 0
        if dist[u] == INF:
            continue
        for i in range(len(e[u])):
            v = e[u][i].to
            w = e[u][i].w
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if inq[v] == 0:
                    heapq.heappush(q, v)
                    inq[v] = 1

n, m, s = map(int, input().split())
for i in range(m):
    u, v, w = map(int, input().split())
    e[u].append(Edge(v, w))
spfa(s)
for i in range(1, n+1):
    if dist[i] == INF:
        print("-1", end=" ")
    else:
        print(dist[i], end=" ")

总结

Dijkstra：适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度 O(E+VlgV) BellmanFord：适用于权值有负值的图的单源最短路径，并且能够检测负圈，复杂度 O(VE) SPFA：适用于权值有负值，且没有负圈的图的单源最短路径。论文中的复杂度为 O(kE), 其中 k 为每个节点进入队列的次数，且 k 一般 <=2，但此处的复杂度证明是有问题的，其实 SPFA 的最坏情况应该是 O(VE)。 Floyd：每对节点之间的最短路径。

所以：

单源最短路 (1)当权值为非负时，用 Dijkstra。 (2)当权值有负值，且没有负圈，则用 SPFA。SPFA 能检测负圈，但是不能输出负圈。 (3)当权值有负值，而且可能存在负圈需要输出，则用 BellmanFord。能够检测并输出负圈。多源最短路使用 Floyd

最小生成树

在无向图中，连通而且不含有圈（环路）的图，称为树。最小生成树 MST：一个有 n 个结点的连通图的生成树是原图的极小连通子图，包含原图中的所有 n 个结点，并且边的权值之和最小。

Prim 算法

对点进行贪心操作：“最近的邻居一定在 MST 上”。从任意一个点 u 开始，把距离它最近的点 v 加入到 MST 中；下一步，把距离 {u, v} 最近的点 w 加入到 MST 中；继续这个过程，直到所有点都在 MST 中。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
vector<int> demo;
int closest[MAXN],lowcost[MAXN],m,n;//m为节点的个数，n为边的数量
int G[MAXN][MAXN];//邻接矩阵
int prim()
{
    for(int i=0;i<m;i++)
    {
        lowcost[i] = INF;
    }
    for(int i=0;i<m;i++)
    {
        closest[i] = 0;
    }
    closest[0] = -1;//加入第一个点，-1表示该点在集合U中，否则在集合V中
    int num = 0,ans = 0,e = 0;//e为最新加入集合的点
    while (num < m-1)//加入m-1条边
    {
        int micost = INF,miedge = -1;
        for(int i=0;i<m;i++)
        if(closest[i] != -1)
        {
            int temp = G[e][i];
            if(temp < lowcost[i])
            {
                lowcost[i] = temp;
                closest[i] = e;
            }
            if(lowcost[i] < micost)
            micost = lowcost[miedge=i];
        }
        ans += micost;
        demo.push_back(micost);
        closest[e = miedge] = -1;
        num++;
    }
    return ans;
}

int main()
{

    scanf("%d %d", &m, &n);
    memset(G,INF,sizeof(G));
    for(int i = 0; i < n; ++i)
    {
       int a,b,c;
       cin>>a>>b>>c;

       G[b][a]=G[a][b]=c;

    }

    cout<<prim()<<endl;
    for(int i=0;i<m-1;i++) cout<<demo[i]<<" ";
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static final int INF = 0x3f3f3f3f;
    private static final int MAXN = 1005;
    private static int[] closest = new int[MAXN];
    private static int[] lowcost = new int[MAXN];
    private static int[][] G = new int[MAXN][MAXN];
    private static int m;
    private static List demo = new ArrayList();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        int n = scanner.nextInt();

        for (int i = 0; i < n; ++i) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            G[b][a] = G[a][b] = c;
        }

        System.out.println(prim());
        for (int i = 0; i < m - 1; i++) {
            System.out.print(demo.get(i) + " ");
        }
    }

    private static int prim() {
        for (int i = 0; i < m; i++) {
            lowcost[i] = INF;
            closest[i] = 0;
        }

        closest[0] = -1;//加入第一个点，-1表示该点在集合U中，否则在集合V中
        int num = 0, ans = 0, e = 0;//e为最新加入集合的点

        while (num < m - 1)//加入m-1条边
        {
            int micost = INF, miedge = -1;
            for (int i = 0; i < m; i++) {
                if (closest[i] != -1) {
                    int temp = G[e][i];
                    if (temp < lowcost[i]) {
                        lowcost[i] = temp;
                        closest[i] = e;
                    }
                    if (lowcost[i] < micost) {
                        micost = lowcost[miedge = i];
                    }
                }
            }
            ans += micost;
            demo.add(micost);
            closest[e = miedge] = -1;
            num++;
        }
        return ans;
    }
}

Python

INF = 0x3f3f3f3f
MAXN = 1005
closest = [0] * MAXN
lowcost = [0] * MAXN
G = [[INF] * MAXN for _ in range(MAXN)]
demo = []

m,n = map(int, input().split())

for i in range(n):
    a,b,c = map(int, input().split())
    G[b][a]=G[a][b]=c

def prim():
    global closest, lowcost, G, m
    for i in range(m):
        lowcost[i] = INF
        closest[i] = 0

    closest[0] = -1
    num = 0
    ans = 0
    e = 0

    while num < m-1:
        micost = INF
        miedge = -1
        for i in range(m):
            if closest[i] != -1:
                temp = G[e][i]
                if temp < lowcost[i]:
                    lowcost[i] = temp
                    closest[i] = e
                if lowcost[i] < micost:
                    miedge=i
                    micost = lowcost[miedge]
        ans += micost
        demo.append(micost)
        e = miedge
        closest[e] = -1
        num += 1

    return ans

print(prim())
for i in range(m - 1): print(demo[i], end=' ')

kruskal 算法

对边进行贪心操作：“最短的边一定在 MST 上”。从最短的边开始，把它加入到 MST 中；在剩下的边中找最短的边，加入到 MST 中；继续这个过程，直到所有点都在 MST 中。

kruskal 算法的 2 个关键技术：（1）对边进行排序。（2）判断圈，即处理连通性问题。这个问题用并查集简单而高效，并查集是 kruskal 算法的实现基础。

初始时最小生成树 MST 为空。开始的时候，每个点属于独立的集。

按边长从小到大进行边的遍历操作：

尝试将最小边加入最小生成树：

如果边的两个端点属于同一个集合，就说明这两个点已经被加入最小生成树。则不能将边加入，否则就会生成一个环。
如果两个端点不属于同一个集合，就说明该点还未纳入最小生成树，此边可以加入。

重复上述操作，直到加入 n-1 条边。

kruskal 算法的复杂度包括两部分：对边的排序 O(ElogE)，并查集的操作 O(E)，一共是 O(ElogE + E)，约等于 O(ElogE)，时间主要花在排序上。

如果图的边很多，kruskal 的复杂度要差一些。kruskal 适用于稀疏图，prim 适合稠密图。

模板如下：

#include <bits/stdc++.h>
using namespace std;

int n,m;
int father[1100000];
struct node
{
    int x;
    int y;
    int k;
} Q[1100000];

int find(int x)
{
    if (father[x] == x)
        return x;
    return father[x] = find(father[x]);
}
bool cmp(node a, node b)
{
    return a.k < b.k;
}
int main()
{
    scanf("%d %d", &n, &m);

    int cont = 0,
        sum = 0, st = 0;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &Q[i].x, &Q[i].y, &Q[i].k);
        cont += Q[i].k;
    }
    sort(Q, Q + m, cmp);
    for (int i = 1; i <= n; i++)
        father[i] = i;
    for (int i = 0; i < m; i++)
    {
        int tx = find(Q[i].x);
        int ty = find(Q[i].y);
        if (tx != ty)
        {
            sum += Q[i].k;
            st++;
            father[tx] = ty;
            if (st == n - 1)
                break;
        }
    }
    printf("%d\n", sum);
    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] father;
    static Node[] Q;

    static class Node {
        int x;
        int y;
        int k;

        public Node(int x, int y, int k) {
            this.x = x;
            this.y = y;
            this.k = k;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        father = new int[n + 1];
        Q = new Node[m];

        int cont = 0, sum = 0, st = 0;
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int k = scanner.nextInt();
            Q[i] = new Node(x, y, k);
            cont += k;
        }
        Arrays.sort(Q, (a, b) -> a.k - b.k);
        for (int i = 1; i <= n; i++)
            father[i] = i;
        for (int i = 0; i < m; i++) {
            int tx = find(Q[i].x);
            int ty = find(Q[i].y);
            if (tx != ty) {
                sum += Q[i].k;
                st++;
                father[tx] = ty;
                if (st == n - 1)
                    break;
            }
        }
        System.out.println(sum);
    }

    static int find(int x) {
        if (father[x] == x)
            return x;
        return father[x] = find(father[x]);
    }

}

Python

n, m = map(int, input().split())

father = [i for i in range(n+1)]

Q = []

cont = 0
sum = 0
st = 0

for i in range(m):
    x, y, k = map(int, input().split())
    Q.append({'x': x, 'y': y, 'k': k})
    cont += k

Q.sort(key=lambda x:x['k'])

def find(x):

    if father[x] == x :
        return x
    father[x] = find(father[x])
    return father[x]

for i in range(m):
    tx = find(Q[i]['x'])
    ty = find(Q[i]['y'])
    if tx != ty:
        sum += Q[i]['k']
        st += 1
        father[tx] = ty
        if st == n - 1:
            break
print(sum)

图论例题

蓝桥王国 lanqiaoOJ 题号 1122

题目描述

蓝桥王国一共有 $N$ 个建筑和 $M$ 条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为 $1 \sim N$。（其中皇宫的编号为 1）国王想让小明回答从皇宫到每个建筑的最短路径是多少，但紧张的小明此时已经无法思考，请你编写程序帮助小明回答国王的考核。

输入描述

输入第一行包含 2 个正整数 $N,M$。第 2 到 $M+1$ 行每行包含三个正整数 $u,v,w$，表示 $u \to v$ 之间存在一条距离为 $w$ 的路。$1 \leq N \leq 3 \times 10^5$，$1 \leq M \leq 10^6$，$1 \leq u_i , v_i \leq N$，$0 \leq w_i \leq 10^9$。

输出描述

输出仅一行，共 $N$ 个数，分别表示从皇宫到编号为 $1 \sim N$ 建筑的最短距离，两两之间用空格隔开。（如果无法到达则输出 −1）

解题思路:

本题为单源最短路的模板题，直接套模板即可，本题我们采用 Dijkstra。

C++ 语言描述:

#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
//这样定义INF的好处是: INF <= INF+x
const int N= 3e5+2;
struct edge{
    int from, to; long long w; //起点，终点，权值。起点from并没有用到，e[i]的i就是from
    edge(int a, int b,long long c){from=a; to=b; w=c;}
};
vector<edge>e[N];          //用于存储图
struct s_node{
    int id; long long n_dis;   //id：结点；n_dis：这个结点到起点的距离
    s_node(int b,long long c){id=b; n_dis=c;}
    bool operator < (const s_node & a) const
    { return n_dis > a.n_dis;}
};
int n,m;
int pre[N];                                //记录前驱结点，用于生成路径
void print_path(int s, int t) {            //打印从s到t的最短路
    if(s==t){ printf("%d ", s); return; }  //打印起点
    print_path(s, pre[t]);                 //先打印前一个点
    printf("%d ", t);                      //后打印当前点。最后打印的是终点t
}
long long  dis[N];         //记录所有结点到起点的距离
void dijkstra(){
    int s = 1;             //起点s是1
    bool done[N]; //done[i]=true表示到结点i的最短路径已经找到
    for (int i=1;i<=n;i++) {dis[i]=INF; done[i]=false; }    //初始化
    dis[s]=0;                           //起点到自己的距离是0
    priority_queue <s_node> Q;          //优先队列，存结点信息
    Q.push(s_node(s, dis[s]));          //起点进队列
    while (!Q.empty())   {
        s_node u = Q.top();             //pop出距起点s距离最小的结点u
        Q.pop();
        if(done[u.id])  continue;       //丢弃已经找到最短路径的结点。即集合A中的结点
        done[u.id]= true;
        for (int i=0; i<e[u.id].size(); i++) {  //检查结点u的所有邻居
            edge y = e[u.id][i];         //u.id的第i个邻居是y.to
            if(done[y.to])  continue;    //丢弃已经找到最短路径的邻居结点
            if (dis[y.to] > y.w + u.n_dis) {
                dis[y.to] = y.w + u.n_dis;
                Q.push(s_node(y.to, dis[y.to]));  //扩展新的邻居，放到优先队列中
                pre[y.to]=u.id;  //如果有需要，记录路径
            }
        }
    }
    // print_path(s,n);          //如果有需要，打印路径: 起点1，终点n
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)    e[i].clear();
    while (m--) {
        int u,v,w;  scanf("%d%d%lld",&u,&v,&w);
        e[u].push_back(edge(u,v,w));
     // e[v].push_back(edge(v,u,w));    //本题是单向道路
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(dis[i]>=INF)  cout<<"-1 ";
        else   printf("%lld ", dis[i]);
    }
}

Python 语言描述:

import heapq

INF = 0x3f3f3f3f3f3f3f3f
N = 300002

class Edge:
    def __init__(self, fr, to, w):
        self.fr = fr
        self.to = to
        self.w = w

class SNode:
    def __init__(self, id, n_dis):
        self.id = id
        self.n_dis = n_dis

    def __lt__(self, other):
        return self.n_dis < other.n_dis

def print_path(s, t):
    if s == t:
        print(s, end=" ")
        return
    print_path(s, pre[t])
    print(t, end=" ")

def dijkstra():
    s = 1
    done = [False] * N
   

 dis = [INF] * N
    pre = [-1] * N
    dis[s] = 0
    pq = []
    heapq.heappush(pq, SNode(s, dis[s]))
    while pq:
        u = heapq.heappop(pq)
        if done[u.id]:
            continue
        done[u.id] = True
        for y in e[u.id]:
            if done[y.to]:
                continue
            if dis[y.to] > y.w + u.n_dis:
                dis[y.to] = y.w + u.n_dis
                heapq.heappush(pq, SNode(y.to, dis[y.to]))
                pre[y.to] = u.id
    for i in range(1, n+1):
        if dis[i] >= INF:
            print("-1", end=" ")
        else:
            print(dis[i], end=" ")

n, m = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(m):
    u, v, w = map(int, input().split())
    e[u].append(Edge(u, v, w))

dijkstra()

Java 语言描述:

import java.util.*;
import java.io.*;

public class Main {
    static final long INF = 0x3f3f3f3f3f3f3f3fL;
    static final int N = 300005;
    static ArrayList<Edge>[] e = new ArrayList[N];
    static int n, m;
    static int[] pre = new int[N];
    static long[] dis = new long[N];
    static boolean[] done = new boolean[N];

    static class Edge {
        int from, to;
        long w;

        Edge(int a, int b, long c) {
            from = a;
            to = b;
            w = c;
        }
    }

    static class SNode implements Comparable<SNode> {
        int id;
        long n_dis;

        SNode(int b, long c) {
            id = b;
            n_dis = c;
        }

        public int compareTo(SNode o) {
            return Long.compare(n_dis, o.n_dis);
        }
    }

    static void printPath(int s, int t) {
        if (s == t) {
            System.out.print(s + " ");
            return;
        }
        printPath(s, pre[t]);
        System.out.print(t + " ");
    }

    static void dijkstra() {
        int s = 1;
        PriorityQueue<SNode> Q = new PriorityQueue<>();
        Arrays.fill(dis, INF);
        dis[s] = 0;
        Q.offer(new SNode(s, dis[s]));
        while (!Q.isEmpty()) {
            SNode u = Q.poll();
            if (done[u.id])
                continue;
            done[u.id] = true;
            for (Edge y : e[u.id]) {
                if (done[y.to])
                    continue;
                if (dis[y.to] > y.w + u.n_dis) {
                    dis[y.to] = y.w + u.n_dis;
                    Q.offer(new SNode(y.to, dis[y.to]));
                    pre[y.to] = u.id;
                }
            }
        }
        // printPath(s, n);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= n; i++)
            e[i] = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            long w = Long.parseLong(st.nextToken());
            e[u].add(new Edge(u, v, w));
            // e[v].add(new Edge(v, u, w)); //本题是单向道路
        }
        dijkstra();
        for (int i = 1; i <= n; i++) {
            if (dis[i] >= INF)
                System.out.print("-1 ");
            else
                System.out.print(dis[i] + " ");
        }
    }
}

随机数据下的最短路问题 lanqiaoOJ 题号 1366

题目描述

给定 $N$ 个点和 $M$ 条单向道路，每条道路都连接着两个点，每个点都有自己编号，分别为 $1 \sim N$。问你从 $S$ 点出发，到达每个点的最短路径为多少。

输入描述

输入第一行包含三个正整数 $N,M,S$。第 2 到 $M+1$ 行每行包含三个正整数 $u,v,w$，表示 $u \to v$ 之间存在一条距离为 $w$ 的路。$1 \leq N \leq 5 \times 10^3$，$1 \leq M \leq 5 \times 10^4$，$1 \leq u_i, v_i \leq N$，$0 \leq w_i \leq 10^9$。

输出描述

输出仅一行，共 $N$ 个数，分别表示从编号 $S$ 到编号为 $1 \sim N$ 点的最短距离，两两之间用空格隔开。（如果无法到达则输出 −1）

解题思路:

本题为单源最短路的模板题，直接套模板即可，本题我们采用 SPFA。

C++ 语言描述:

#include<bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3+10;
struct edge{
    int to;    long long w;
    edge(int tt,long long ww) {to = tt; w = ww;}
};
long long dist[N];
int inq[N];
vector<edge> e[N];
void spfa(int s){
    memset(dist,0x3f,sizeof(dist));
    dist[s] = 0;      //起点到自己的距离是0
    queue<int> q;
    q.push(s);        //从s开始，s进队列
    inq[s] = 1;       //起点在队列中
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = 0;   //u已经不在队列中
        if(dist[u] == INF)     continue;
        for(int i = 0;i < e[u].size();i++) {   //遍历u的邻居
            int v = e[u][i].to;
            long long w = e[u][i].w;
            if(dist[v] > dist[u]+w) {         //u的第i个邻居v，它借道u，到s更近
                dist[v] = dist[u]+w;          //更新邻居v到s的距离
                if(!inq[v]) {      //邻居v更新状态了，但v不在队列中，放进队列
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
}
int main(){
    int n,m,s;cin>>n>>m>>s;
    for(int i = 1;i <= m;i++)    {
        int u,v; long long w;
        cin>>u>>v>>w;
        e[u].push_back(edge(v,w));
    }
    spfa(s);
    for(int i = 1;i <= n;i++) {
        if(dist[i]==INF)  cout << -1;
        else              cout << dist[i];
        if(i != n)        cout << " ";
        else              cout << endl;
    }
    return 0;
}

Python 语言描述:

import heapq

INF = 0x3f3f3f3f3f3f3f3f
N = 5010

class Edge:
    def __init__(self, to, w):
        self.to = to
        self.w = w

dist = [INF] * N
inq = [0] * N
e = [[] for _ in range(N)]

def spfa(s):
    global dist
    global inq
    dist = [INF] * N
    dist[s] = 0
    q = []
    heapq.heappush(q, s)
    inq[s] = 1
    while q:
        u = heapq.heappop(q)
        inq[u] = 0
        if dist[u] == INF:
            continue
        for i in range(len(e[u])):
            v = e[u][i].to
            w = e[u][i].w
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if inq[v] == 0:
                    heapq.heappush(q, v)
                    inq[v] = 1

n, m, s = map(int, input().split())
for i in range(m):
    u, v, w = map(int, input().split())
    e[u].append(Edge(v, w))
spfa(s)
for i in range(1, n+1):
    if dist[i] == INF:
        print("-1", end=" ")
    else:
        print(dist[i], end=" ")

Java 语言描述:

import java.util.*;

public class Main {
    static final long INF = 0x3f3f3f3f3f3f3f3fL;
    static final int N = 5010;

    static long[] dist = new long[N];
    static int[] inq = new int[N];
    static List<edge>[] e = new ArrayList[N];

    static class edge {
        int to;
        long w;

        public edge(int tt, long ww) {
            to = tt;
            w = ww;
        }
    }

    static void spfa(int s) {
        Arrays.fill(dist, INF);
        dist[s] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        inq[s] = 1;
        while (!q.isEmpty()) {
            int u = q.poll();
            inq[u] = 0;
            if (dist[u] == INF) continue;
            for (int i = 0; i < e[u].size(); i++) {
                int v = e[u].get(i).to;
                long w = e[u].get(i).w;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    if (inq[v] == 0) {
                        q.add(v);
                        inq[v] = 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int s = in.nextInt();
        for (int i = 1; i <= n; i++) {
            e[i] = new ArrayList<>();
        }
        for (int i = 1; i <= m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            long w = in.nextLong();
            e[u].add(new edge(v, w));
        }
        spfa(s);
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) System.out.print("-1 ");
            else System.out.print(dist[i] + " ");
        }
    }
}

路径 OJ 编号 1460

图片描述

解题思路:

填空题对时间没有要求，用最简单的 floyd

C++ 语言描述:

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3000;
const ll INF = 1e18;
ll mp[N][N];
void floyd(int n){
    for(int k = 1;k <= n;k++)
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
int main(){
    int n = 2021;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(i == j) mp[i][j] = 0;
            else if(abs(i - j)<=21) mp[i][j]=mp[j][i]=i*j/__gcd(i, j);
            else mp[i][j] = mp[j][i] = INF;
        }
    }
    floyd(n);
    cout << mp[1][2021];
    return 0;
}

Python 语言描述:

import math

def lcm(a, b):
    return int(a * b / math.gcd(a, b))

n = 2021
g = [[0 for i in range(1, n + 2)] for j in range(1, n + 2)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            g[i][j] = g[j][i] = 0
        elif abs(i - j) <= 21:
            g[i][j] = g[j][i] = lcm(i, j)
        else:
            g[i][j] = 1000000000
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if g[i][j] > g[i][k] + g[k][j]:
                g[i][j] = g[i][k] + g[k][j]
print(g[1][n])

Java 语言描述:

public class Main {

    static final int n = 2021;

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    public static void main(String[] args) {
        int[][] floyd = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n && j < i + 22; j++)
                floyd[i][j] = floyd[j][i] = lcm(i + 1, j + 1);
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (floyd[i][k] != 0 && floyd[k][j] != 0 && (floyd[i][j] == 0 || floyd[i][k] + floyd[k][j] < floyd[i][j]))
                        floyd[i][j] = floyd[i][k] + floyd[k][j];
        System.out.println(floyd[0][n - 1]);
    }
}

出差

图片描述

解题思路:

图片描述

我们这里给大家一个朴素的 dijkstra 的模板，大家感受一下，优先队列到底优化的那一部分。

C++ 语言描述:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

//邻接矩阵
int gra[N][N];
int dist[N];
int g[N];
bool st[N];
int n,m;
//朴素版dijkstra
int dijkstra()
{
     memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + gra[t][j]);
        st[t] = true;
    }
    return dist[n];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>g[i];
    g[n]=0;
    memset(gra, 0x3f, sizeof gra);
    for(int i=1;i<=m;++i){
        int u,v,c;
        cin>>u>>v>>c;
        gra[u][v]=g[v]+c;
        gra[v][u]=g[u]+c;
    }
    cout<<dijkstra()<<endl;
    return 0;
}

Python 语言描述:

import sys
from typing import List

n, m = map(int, input().split())

# 邻接矩阵
gra = [[float('inf')] * (n+1) for _ in range(n+1)]
dist = [float('inf')] * (n+1)
g = [0] + list(map(int, input().split()))
g[n] = 0
st = [False] * (n+1)

# 朴素版 Dijkstra
def dijkstra() -> int:
    dist[1] = 0

    for _ in range(n - 1):
        t = -1
        for j in range(1, n + 1):
            if not st[j] and (t == -1 or dist[t] > dist[j]):
                t = j
        for j in range(1, n + 1):
            dist[j] = min(dist[j], dist[t] + gra[t][j])
        st[t] = True
    return dist[n]

for _ in range(m):
    u, v, c = map(int, input().split())
    gra[u][v] = g[v] + c
    gra[v][u] = g[u] + c

print(dijkstra())

Java 语言描述:

import java.util.*;
public class Main {
    static int N = 1010;
    static int[][] gra = new int[N][N];
    static int[] dist = new int[N];
    static int[] g = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 1; i <= n; ++i) {
            g[i] = scan.nextInt();
        }
        g[n] = 0;
        for(int i = 0 ; i < N ; i ++) Arrays.fill(gra[i], 0x3f3f3f);
        for(int i = 1; i <= m; ++i) {
            int u = scan.nextInt(), v = scan.nextInt(), c = scan.nextInt();
            gra[u][v] = g[v] + c;
            gra[v][u] = g[u] + c;
        }
        System.out.println(dijkstra());
    }
    private static int dijkstra() {
        Arrays.fill(dist, 10000000);
        dist[1] = 0;
        for(int i = 0; i < n - 1; i++) {
            int t = -1;
            for(int j = 1; j <= n; j++) {
                if(!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            if(t == -1) break;
            for(int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + gra[t][j]);
            }
            st[t] = true;
        }
        return dist[n];
    }
}

聪明的猴子

图片描述

解题思路:

图片描述

C++ 语言描述:

#include <bits/stdc++.h>
using namespace std;
int a[5005], x[5005], y[5005], f[5005];
struct Edge{
    int x;
    int y;
    double w;
}edge[1000005];
int find(int x){
    if (x == f[x])
        return x;
    f[x] = find(f[x]);
    return f[x];
}
int cmp(Edge a, Edge b){
    return a.w < b.w;
}
void merge(int x, int y){
    int xx = find(x);
    int yy = find(y);
    if (xx != yy)
        f[yy] = xx;
}
int main(){
    int cnt = 0;
    int n, m;
    cin >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            double w = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
            edge[++cnt] = {i, j, w};
        }
    }
    sort(edge + 1, edge + cnt + 1, cmp);
    int num = 0;
    double max = 0.0;
    for (int i = 1; i <= cnt; i++){
        if (find(edge[i].x)!=find(edge[i].y)){
            merge(edge[i].x, edge[i].y);
            num++;
            max = max>=edge[i].w?max:edge[i].w;
        }
        if (num == n - 1)
            break;
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
        if (a[i] >= max)
            ans++;
    cout << ans << endl;
    return 0;
}

Python 语言描述:

import math

class Edge:
    x = 0
    y = 0
    w = 0.0
    def __init__(self, x, y, w):
        self.x = x
        self.y = y
        self.w = w

def find(x):
    if f[x]==x:
        return f[x]
    else:
        f[x] = find(f[x])
        return f[x]

def merge(x,y):
    xx = find(x)
    yy = find(y)
    if xx!=yy:
        f[yy] = xx

if __name__ == '__main__':
    m = int(input())
    a = list(map(int, input().split()))
    n = int(input())
    x = [0 for i in range(n + 2)]
    y = [0 for i in range(n + 2)]
    for i in range(n):
        b = list(map(int, input().split()))
        x[i + 1] = b[0]
        y[i + 1] = b[1]
    edge_list = []
    maxvalue = 0
    num = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            w = math.sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]))
            edge =  Edge(i, j, w)
            edge_list.append(edge)

    edge_list.sort(key=lambda x: x.w)
    f = [i for i in range(n + 1)]
    for i in edge_list:
        if find(i.x)!=find(i.y):
            merge(i.x,i.y)
            maxvalue = max(maxvalue,i.w)
            num+=1
            if num==n-1:
                break
    ans = 0
    for i in range(m):
        if a[i]>=maxvalue:
            ans+=1
    print(ans)

Java 语言描述:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    static int ans = 0;
    static int n;
    static int[] a;
    static int m;
    static int[] x;
    static int[] y;
    static double max;
    static int[] f;
    static int num = 0;
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException{
        m = Integer.parseInt(in.readLine().trim());
        a = new int[m];
        String[] s = in.readLine().trim().split(" ");
        for(int i=0;i<m;i++)
            a[i] = Integer.parseInt(s[i]);
        n = Integer.parseInt(in.readLine().trim());
        x = new int[n];
        y = new int[n];
        for(int i=0;i<n;i++) {
            s = in.readLine().trim().split(" ");
            x[i] = Integer.parseInt(s[0]);
            y[i] = Integer.parseInt(s[1]);
        }
        ArrayList<Edge> list = new ArrayList<>();
        for(int i=0;i<n-1;i++) {
            for(int j=i+1;j<n;j++) {
                double l = Math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                Edge edge = new Edge(i, j, l);
                list.add(edge);
            }
        }
        Collections.sort(list);
        f = new int[n];
        for(int i=0;i<n;i++)
            f[i] = i;
        for(int i=0;i<list.size();i++) {
            Edge e = list.get(i);
            if(find(e.x)!=find(e.y)) {
                merge(e.x,e.y);
                max = Math.max(max, e.w);
                num++;
                if(num==n-1)
                    break;
            }
        }
        for(int i=0;i<m;i++)
            if(a[i]>=max)
                ans++;
        System.out.println(ans);
    }
    static int find(int x) {
        if(f[x] == x)
            return f[x];
        f[x] = find(f[x]);
        return f[x];
    }
    static void merge(int x,int y) {
        int xx = find(x);
        int yy = find(y);
        if(xx!=yy)
            f[yy] = xx;
    }
}
class Edge implements Comparable<Edge>{
    int x;
    int y;
    double w;
    public Edge(int x, int y, double w) {
        super();
        this.x = x;
        this.y = y;
        this.w = w;
    }
    @Override
    public int compareTo(Edge o) {
        // TODO Auto-generated method stub
        return this.w>o.w?1:-1;
    }
}

通电

图片描述

解题思路:

给了你 n 个节点，又给了你 n 个基点之间相互连接需要多少钱，现在要 n 个村庄都通电，只需要保证 n 个节点构成连通子图即可。

最小的连通子图是树，也就是构造一棵树，那么在图上构造一棵最最少花费的树的问题即为最小生成树。

C++ 语言描述:

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
vector<int> demo;
double closest[MAXN], lowcost[MAXN];
int m, n;             // m为节点的个数，n为边的数量
double G[MAXN][MAXN]; // 邻接矩阵
double prim()
{
    for (int i = 0; i < m; i++)
    {
        lowcost[i] = INF;
    }
    for (int i = 0; i < m; i++)
    {
        closest[i] = 0;
    }
    closest[0] = -1;             // 加入第一个点，-1表示该点在集合U中，否则在集合V中
    int num = 0,  e = 0; // e为最新加入集合的点
    double ans=0;
    while (num < m - 1)          // 加入m-1条边
    {
        int miedge = -1;
        double micost = INF;
        for (int i = 0; i < m; i++)
            if (closest[i] != -1)
            {
                double temp = G[e][i];
                if (temp < lowcost[i])
                {
                    lowcost[i] = temp;
                    closest[i] = e;
                }
                if (lowcost[i] < micost)
                    micost = lowcost[miedge = i];
            }
        ans += micost;
        demo.push_back(micost);
        closest[e = miedge] = -1;
        num++;
    }
    return ans;
}

struct node
{
    double x, y, h;
} dis[MAXN];

double getDistance(node a, node b)
{
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)) + pow(a.h - b.h, 2);
}

int main()
{

    scanf("%d", &m);

    for (int i = 0; i < m; i++)
        scanf("%lf%lf%lf", &dis[i].x, &dis[i].y, &dis[i].h);
    for (int i = 0; i < m - 1; i++)
        for (int j = i + 1; j < m; j++)
        {
            G[i][j] = getDistance(dis[i], dis[j]);
            G[j][i] = G[i][j];
        }

    printf("%.2lf", prim());
    // for (int i = 0; i < m - 1; i++)
    //     cout << demo[i] << " ";
    return 0;
}

Python 语言描述:

import os
import sys

import math
def caculate(x1,y1,h1,x2,y2,h2):
    return math.sqrt( (x1-x2)**2+(y1-y2)**2)+(h1-h2)**2\

def find(x):
    if x!=ufs[x]:
        ufs[x]=find(ufs[x])
    return ufs[x]

def kruskal():
    global ufs
    ufs=list(range(n+1))
    my_brige.sort(key=lambda x:x[2])
    ans=0
    cnt=0
    for a,b,w in my_brige:
        x=find(a)
        y=find(b)
        if x==y:
            continue
        cnt+=1
        ans+=w
        ufs[x]=y

        if cnt==n-1:
            return ans



n=int(input())
brige=[[] for i in range(n+1)]
for i in range(1,n+1):
    x,y,h=map(int,input().split())
    brige[i]=(x,y,h)


my_brige=[]
for i in range(1,n):
    for j in range(i+1,n+1):
        x1,y1,h1=brige[i]
        x2,y2,h2=brige[j]
        w=caculate(x1,y1,h1,x2,y2,h2)
        my_brige.append((i,j,w))
ans=kruskal()
print("{:.2f}".format(ans))

Java 语言描述:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int N = 1010;
    static List<Node> list = new ArrayList<>();
    static int[] x = new int[N], y = new int[N], z = new int[N];
    static int n;
    //并查集数组
    static int[] q = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            z[i] = sc.nextInt();
        }
        //建边  任意两个村庄都要建边
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int l = x[i] - x[j];
                int r = y[i] - y[j];
                double c = z[i] - z[j];
                // i 村庄 到  j 村庄的 距离
                double s = Math.sqrt(l * l + r * r) + c * c;
                list.add(new Node(i, j, s));
            }
        }
        // 核心：按权值排序
        list.sort(Comparator.comparingDouble(a -> a.w));
        for (int i = 0; i < n; i++) {
            q[i] = i;
        }
        //记录权重之和，答案
        double res = 0;
        for (int i = 0; i < list.size(); i++) {
            int a = list.get(i).a;
            int b = list.get(i).b;
            double w = list.get(i).w;
            a = find(a);
            b = find(b);
            if (a != b) {
                q[a] = b;
                res += w;
            }
        }
        System.out.printf("%.2f", res);
    }

    static int find(int x) {
        if (q[x] != x) q[x] = find(q[x]);
        return q[x];
    }

    static class Node {
        int a, b;
        double w;

        public Node(int a, int b, double w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
}

机房

这天, 小明在机房学习。

他发现机房里一共有 $n$ 台电脑, 编号为 1 到 $n$, 电脑和电脑之间有网线连接, 一共有 $n-1$ 根网线将 $n$ 台电脑连接起来使得任意两台电脑都直接或者间接地相连。

小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑用网线直接连接了另外 $d$ 台电脑, 那么任何经过这台电脑的信息都会延迟 $d$ 单位时间 (发送方和接收方也会产生这样的延迟, 当然如果发送方和接收方都是同一台电脑就只会产生一次延迟)。

小明一共产生了 $m$ 个疑问: 如果电脑 $u_{i}$ 向电脑 $v_{i}$ 发送信息, 那么信息从 $u_{i}$ 传到 $v_{i}$ 的最短时间是多少?

解题思路:

还是一道比较明显的求LCA(最近公共祖先)模型的题目,我们可以使用多种方法来解决该问题，这里我们使用更好写的离线的tarjan算法来解决该问题。

除去tarjan算法必用的基础数组，我们还有一个数组d[],d[i]记录的是每个点的出度，也就是它的延迟时间，以及数组w[],w[i]的含义是点i到根节点的延迟时间。在通过dfs求出每个点i的w[i]以后，在tarjan中我们该如何求出两点的延迟时间呢？

我们设点i到j的延迟时间为$f(x)$,当我们求得i与j的最近公共祖先为anc，我们首先让$f(x)=w[i]+w[j]$,但很明显，我们多加了两遍$w[anc]$，所以我们需要减去两倍的$w[anc]$，但延迟时间还包括经过anc的时间，所以还得加上一个$d[anc]$。此处请结合w[]和d[]的含义理解。 最后能得出式子:$f(x)=w[i]+w[h]-w[anc]*2+d[anc]$ 我们利用这个式子在tarjan函数中就能得出每个询问的答案，当然对于起始和结束都在同一个节点的情况下,它的答案就是当前节点的出度，我们可以进行特判一下。输入输出较多，建议使用scanf和printf进行输入输出。

时间复杂度:dfs：每个点遍历一次,复杂度级别$O(n)$,tarjan算法复杂度接近 $O(n+m)$。

C++ 语言描述:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=100010;

unordered_map<int,vector<int>> gra;
int n,m;
//单个点的出度
int d[N];
//记录点i到根节点的延迟
int w[N];
//并查集数组
int q[N];
//记录答案
int res[N];
int st[N];
//存下查询
vector<PII>    query[N];
//并查集查询
int find(int x){
    if(x!=q[x]) q[x]=find(q[x]);
    return q[x];
}

void dfs(int u,int fa)
{
    w[u]+=d[u];
    for(auto g:gra[u]){
        if(g==fa) continue;
        w[g]+=w[u];
        dfs(g,u);
    }
}

void tarjan(int u)
{
    st[u]=1;
    for(auto j:gra[u]){
        if(!st[j])
        {
            tarjan(j);
            q[j]=u;
        }
    }
    for(auto item: query[u]){
        int y=item.first,id=item.second;
        if(st[y]==2){
            int anc=find(y);
            res[id]=w[y]+w[u]-w[anc]*2+d[anc];
        }
    }
    st[u]=2;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n-1;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        gra[a].push_back(b);
        gra[b].push_back(a);
        d[a]++,d[b]++;
    }
    for(int i=0;i<m;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a!=b){
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }else{
            res[i]=d[a];
        }
    }
    dfs(1,-1);
    for(int i=1;i<=n;++i) q[i]=i;
    tarjan(1);
    for(int i=0;i<m;++i) printf("%d\n",res[i]);
    return 0;
}

Python 语言描述:

from collections import defaultdict

gra = defaultdict(list)
d = [0] * 100010
w = [0] * 100010
q = [0] * 100010
res = [0] * 100010
st = [0] * 100010
query = [[] for _ in range(100010)]

def find(x):
    if x != q[x]:
        q[x] = find(q[x])
    return q[x]

def dfs(u, fa):
    w[u] += d[u]
    for g in gra[u]:
        if g == fa:
            continue
        w[g] += w[u]
        dfs(g, u)

def tarjan(u):
    st[u] = 1
    for j in gra[u]:
        if st[j] == 0:
            tarjan(j)
            q[j] = u
    for item in query[u]:
        y, id = item
        if st[y] == 2:
            anc = find(y)
            res[id] = w[y] + w[u] - w[anc] * 2 + d[anc]
    st[u] = 2

n, m = map(int, input().split())
for i in range(n - 1):
    a, b = map(int, input().split())
    gra[a].append(b)
    gra[b].append(a)
    d[a] += 1
    d[b] += 1

for i in range(m):
    a, b = map(int, input().split())
    if a != b:
        query[a].append((b, i))
        query[b].append((a, i))
    else:
        res[i] = d[a]

dfs(1, -1)
for i in range(1, n + 1):
    q[i] = i
tarjan(1)
for i in range(m):
    print(res[i])

Java 语言描述:

import java.util.*;

public class Main {
    static class Pair {
        int first, second;
        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    static Map<Integer, List<Integer>> gra = new HashMap<>();
    static int[] d = new int[100010];
    static int[] w = new int[100010];
    static int[] q = new int[100010];
    static int[] res = new int[100010];
    static int[] st = new int[100010];
    static List<Pair>[] query = new List[100010];

    static int find(int x) {
        if (x != q[x]) q[x] = find(q[x]);
        return q[x];
    }

    static void dfs(int u, int fa) {
        w[u] += d[u];
        for (int g : gra.get(u)) {
            if (g == fa) continue;
            w[g] += w[u];
            dfs(g, u);
        }
    }

    static void tarjan(int u) {
        st[u] = 1;
        for (int j : gra.get(u)) {
            if (st[j] == 0) {
                tarjan(j);
                q[j] = u;
            }
        }
        for (Pair item : query[u]) {
            int y = item.first, id = item.second;
            if (st[y] == 2) {
                int anc = find(y);
                res[id] = w[y] + w[u] - w[anc] * 2 + d[anc];
            }
        }
        st[u] = 2;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            gra.put(i, new ArrayList<>());
            query[i] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            gra.get(a).add(b);
            gra.get(b).add(a);
            d[a]++;
            d[b]++;
        }
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if (a != b) {
                query[a].add(new Pair(b, i));
                query[b].add(new Pair(a, i));
            } else {
                res[i] = d[a];
            }
        }
        dfs(1, -1);
        for (int i = 1; i <= n; i++) {
           q[i] = i;
        }
        tarjan(1);
        for (int i = 0; i < m; i++) {
            System.out.println(res[i]);
        }
    }
}

环境治理

LQ 国拥有 $n$ 个城市, 从 0 到 $n-1$ 编号, 这 $n$ 个城市两两之间都有且仅有一条双向道路连接, 这意味着任意两个城市之间都是可达的。每条道路都有一个属性 $D$, 表示这条道路的灰尘度。当从一个城市 $A$ 前往另一个城市 $B$ 时, 可能存在多条路线, 每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和, LQ 国的人都很讨厌灰尘, 所以他们总会优先选择灰尘度最小的路线。

LQ 国很看重居民的出行环境, 他们用一个指标 $P$ 来衡量 LQ 国的出行环境, $P$ 定义为:

$P=\sum*{i=0}^{n-1} \sum*{j=0}^{n-1} d(i, j)$

其中 $d(i, j)$ 表示城市 $i$ 到城市 $j$ 之间灰尘度最小的路线对应的灰尘度的值。为了改善出行环境, 每个城市都要有所作为, 当某个城市进行道路改善时, 会将与这个城市直接相连的所有道路的灰尘度都减少 1 , 但每条道路都有一个灰尘度的下限值 $L$, 当灰尘度达到道路的下限值时, 无论再怎么改善, 道路的灰尘度也不会再减小了。

具体的计划是这样的:

第 1 天, 0 号城市对与其直接相连的道路环境进行改善;

第 2 天, 1 号城市对与其直接相连的道路环境进行改善;

$\cdots$

第 $n$ 天, $n-1$ 号城市对与其直接相连的道路环境进行改善;

第 $n+1$ 天, 0 号城市对与其直接相连的道路环境进行改善;

第 $n+2$ 天, 1 号城市对与其直接相连的道路环境进行改善;

LQ 国想要使得 $P$ 指标满足 $P \leq Q$ 。请问最少要经过多少天之后, $P$ 指标可以满足 $P \leq Q$ 。如果在初始时就已经满足条件, 则输出 0 ; 如果永远不可能满足, 则输出 $-1$ 。

解题思路:

首先，对于求解P指的公式，我们要清楚，是每个点到其他所有点的最短路径之和相加，这种涉及到任意两点的最短路，加上 $n$ 的最大范围只有100，很明显我们需要想到Floyd算法求任意两点的最短路。

我们并没有一个直观的算法直接求得答案，所以，我们考虑二分答案。 如果改善x天是符合要求的，那么大于x的天数也一定符合，但小于x的天数不一定，所以满足二段性，我们可以二分。

我们用g[][]记录初始道路的灰尘度,m[][]记录每条道路的最低灰尘度,f[][]记录的是在改善x天后的每条道路的环境。这样我们就可以使用二分+Floyd的做法得到答案。

当然这里有一些需要注意的细节问题，当我们改变f[i][j]的值时，相应的也要改变f[j][i]的值，因为任意两点只存在一条双向道路，所以这两个状态应该表示的是同一条道路。每次check时，别忘记将f[][]重置回g[][]，再去减去对于的天数。floyd函数每次跑完后，计算并返回此时的P值。

最开始时我们可以判断每条道路都是最低复杂度的情况下，计算出来的P是否大于Q，如果大于说明肯定无解，直接返回-1即可。二分对于r的上限也需要注意，最多100个点，每个点最大1e5，所以理论上我们只要开到大于1e7以上就不会有问题，否则样例过大时可能会出错。

时间复杂度：$O(n^3log(n*m))$。

C++ 语言描述:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=110;

LL g[N][N];
LL m[N][N];
LL f[N][N];
LL n,q;
LL floyd()
{
    LL a=0;
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            a+=f[i][j];
    return a;
}
//改善X天
bool check(LL x){
    memcpy(f,g,sizeof(g));
    LL h=x/n;
    LL s=x%n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i==j) continue;
            if(i<=s) f[i][j]=max(m[i][j],f[i][j]-h-1);
            else f[i][j]=max(m[i][j],f[i][j]-h);
            f[j][i]=f[i][j];
        }
    }
    return floyd()<=q;
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>g[i][j];
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>m[i][j];
            f[i][j]=m[i][j];
        }
    }
    if(floyd()>q){
        cout<<-1<<endl;
        return;
    }
    LL l=0,r=1000000000;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
}
int main()
{
    solve();
    return 0;
}

Python 语言描述:

import copy
N=110
g=[[0]*N for i in range(N)]
m=[[0]*N for i in range(N)]
f=[[0]*N for i in range(N)]
n,q=map(int,input().split())
def floyd(f):
    a=0
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                f[i][j]=min(f[i][j],f[i][k]+f[k][j])
    for i in range(1,n+1):
        for j in range(1,n+1):
            a=a+f[i][j]
    return a
def check(x,g):
    f=copy.deepcopy(g)
    h=x//n
    s=x%n
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i==j:
                continue
            if i<=s:
                f[i][j]=max(m[i][j],f[i][j]-h-1)
            else:
                f[i][j]=max(m[i][j],f[i][j]-h)
            f[j][i]=f[i][j]
    return  floyd(f)<=q

def solve():
    for i in range(1,n+1):
        l=list(map(int,input().split()))
        for j in range(1,n+1):
            g[i][j]=l[j-1]#灰尘度
    for i in range(1,n+1):
        l = list(map(int, input().split()))
        for j in range(1,n+1):
            m[i][j]=l[j-1]#灰尘度的下限值
            f[i][j]=m[i][j]
    if floyd(f)>q:
        print(-1)
        return
    l,r=0,10000000
    while (l < r):
        mid=(l+r)>>1
        if (check(mid,g)):
            r=mid
        else:
            l=mid+1
    print(r)
solve()

Java 语言描述:

import java.io.*;

public class Main {
    static int N=110;
    static long[][] g=new long[N][N],m=new long[N][N],f=new long[N][N];
    static long n,q;
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter  out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] s=br.readLine().split(" ");
        n=Long.parseLong(s[0]);
        q=Long.parseLong(s[1]);
        for(int i=1;i<=n;++i){
            s=br.readLine().split(" ");
            for(int j=1;j<=n;++j){
                g[i][j]=Long.parseLong(s[j-1]);
            }
        }
        for(int i=1;i<=n;++i){
            s=br.readLine().split(" ");
            for(int j=1;j<=n;++j){
                m[i][j]=Long.parseLong(s[j-1]);
                f[i][j]=m[i][j];
            }
        }
        if(floyd()>q){
            out.println(-1);
            out.flush();
            return;
        }
        long l=0,r=1000000000;
        while(l<r){
            long mid=l+r>>1;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        out.println(r);
        out.flush();
    }
    static long floyd(){
        long a=0;
        for (int k = 1; k <= n; k ++ )
            for (int i = 1; i <= n; i ++ )
                for (int j = 1; j <= n; j ++ )
                    f[i][j] =Math.min(f[i][j], f[i][k] + f[k][j]);

        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                a+=f[i][j];
        return a;
    }
    static boolean check(long x){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j) f[i][j]=g[i][j];
        }
        long h=x/n;
        long s=x%n;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(i==j) continue;
                if(i<=s) f[i][j]=Math.max(m[i][j],f[i][j]-h-1);
                else f[i][j]=Math.max(m[i][j],f[i][j]-h);
                f[j][i]=f[i][j];
            }
        }
        return floyd()<=q;
    }
}

≡