企业官网建设流程全解析

spfa求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出impossible。

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例：

3 3 1 2 5 2 3 -3 1 3 4

输出样例：

2

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Main { static int N =100010,id; static long res=Integer.MAX_VALUE; static int e[]=new int[N]; static int ne[]=new int[N]; static int h[]=new int[N]; static int w[]=new int[N]; static long d[]=new long[N]; static boolean f[]=new boolean[N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]); Arrays.fill(h, -1); for (int i = 0; i < m; i++) { g=br.readLine().split(" "); int a=Integer.parseInt(g[0]),b=Integer.parseInt(g[1]),we=Integer.parseInt(g[2]); add(a, b,we); } for (int i = 2; i <= n; i++) { d[i]=Long.MAX_VALUE; } //bellman-ford的优化版 spfa Queue<Integer> queue=new LinkedList<Integer>(); queue.add(1);f[1]=true; while(!queue.isEmpty()){ int p=queue.poll();f[p]=false; for (int i = h[p]; i!=-1; i=ne[i]) { int j=e[i]; if(d[j]<=d[p]+w[i])continue; d[j]=d[p]+w[i]; if(!f[j]){ f[j]=true; queue.add(j); } } } if(d[n]==Long.MAX_VALUE){ System.out.println("impossible"); }else{ System.out.println(d[n]); } } static void add(int a,int b,int we){ e[id]=b; w[id]=we; ne[id]=h[a]; h[a]=id++; } }

spfa判断负环

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

如果图中存在负权回路，则输出Yes，否则输出No。

数据范围

1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。

输入样例：

3 3 1 2 -1 2 3 4 3 1 -4

输出样例：

Yes

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Main { static int N =100010,id; static long res=Integer.MAX_VALUE; static int e[]=new int[N]; static int ne[]=new int[N]; static int h[]=new int[N]; static int w[]=new int[N]; static int cnt[]=new int[N]; static long d[]=new long[N]; static boolean f[]=new boolean[N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]); Arrays.fill(h, -1); for (int i = 0; i < m; i++) { g=br.readLine().split(" "); int a=Integer.parseInt(g[0]),b=Integer.parseInt(g[1]),we=Integer.parseInt(g[2]); add(a, b,we); } // 把所有点都入队，那第一次更新的时候是哪些点被更新了呢， // 答案是负权边的入边那个点被更新了，假设dt数组初始化为0，那加上一个负边使得dt变小。所以如果要解释dt数组的含义的话，假设图里不存在负权环，那dt[i]的含义就是一个点走过有限次边到达i， // 且走过的距离最小，这个距离就是dt[i]。 //bellman-ford的优化版 spfa Queue<Integer> queue=new LinkedList<Integer>(); for (int i = 1; i <=n; i++) { queue.add(i);f[i]=true; } while(!queue.isEmpty()){ int p=queue.poll();f[p]=false; for (int i = h[p]; i!=-1; i=ne[i]) { int j=e[i]; if(d[j]<=d[p]+w[i])continue; d[j]=d[p]+w[i]; cnt[j]=cnt[p]+1; if(cnt[j]>=n){ System.out.println("Yes"); return; } if(!f[j]){ f[j]=true; queue.add(j); } } } System.out.println("No"); } static void add(int a,int b,int we){ e[id]=b; w[id]=we; ne[id]=h[a]; h[a]=id++; } }

Floyd求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出impossible。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出impossible。

数据范围

1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例：

3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3

输出样例：

impossible 1

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; public class Main { static int N =300,id; static long dis[][]=new long[N][N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]),kk=Integer.parseInt(g[2]); for (int i = 1; i <= n; i++) { Arrays.fill(dis[i],Long.MAX_VALUE); dis[i][i]=0; } for (int i = 0; i < m; i++) { g=br.readLine().split(" "); int a=Integer.parseInt(g[0]),b=Integer.parseInt(g[1]),we=Integer.parseInt(g[2]); dis[a][b]=Math.min(dis[a][b], we); } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if(dis[i][k]!=Long.MAX_VALUE && dis[k][j]!=Long.MAX_VALUE){ dis[i][j]=Math.min(dis[i][j],dis[i][k]+dis[k][j]); } } } } for (int i = 0; i < kk; i++) { g=br.readLine().split(" "); int x=Integer.parseInt(g[0]),y=Integer.parseInt(g[1]); if(dis[x][y]==Long.MAX_VALUE){ System.out.println("impossible"); }else{ System.out.println(dis[x][y]); } } } }

Prim算法求最小生成树

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

数据范围

1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过 10000。

输入样例：

4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4

输出样例：

6

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N =600,id; static long dis[][]=new long[N][N]; static long d[]=new long[N];//表示到选中的点的集合的最短路径 static boolean f[]=new boolean[N]; static int fro[]=new int[N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]); for (int i = 1; i <= n; i++) { Arrays.fill(dis[i],Long.MAX_VALUE); dis[i][i]=0; } for (int i = 2; i <= n; i++) { d[i]=Long.MAX_VALUE; } for (int i = 0; i < m; i++) { g=br.readLine().split(" "); int a=Integer.parseInt(g[0]),b=Integer.parseInt(g[1]),we=Integer.parseInt(g[2]); dis[a][b]=Math.min(dis[a][b], we); dis[b][a]=dis[a][b]; } int sum=0;d[1]=0; long res=0; while(sum<n){ int u=-1; for (int i = 1; i <= n; i++) { if(f[i])continue; if(u==-1 || d[u]>d[i])u=i; } if(d[u]==Long.MAX_VALUE){ System.out.println("impossible"); return; } f[u]=true;sum++; res+=d[u];//累加答案 for (int i = 1; i <= n; i++) { if(f[i]==true)continue; if(dis[u][i]!=Long.MAX_VALUE){ d[i]=Math.min(d[i], dis[u][i]);//直接用 dis[u][i] } } } System.out.println(res); } }

Kruskal算法求最小生成树

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

数据范围

1≤n≤105,
1≤m≤2∗105,
图中涉及边的边权的绝对值均不超过 1000。

输入样例：

4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4

输出样例：

6

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N =2*100010,id; static Node node[]=new Node[N]; static int p[]=new int[N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[]=br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]); for (int i = 0; i < m; i++) { g=br.readLine().split(" "); int a=Integer.parseInt(g[0]),b=Integer.parseInt(g[1]),we=Integer.parseInt(g[2]); if(a==b)continue; node[id++]=new Node(a, b, we); } for (int i = 1; i <= n; i++) { p[i]=i; } Arrays.sort(node,0,id); int sum=0;long res=0; for (int i = 0; i < id && sum<n-1; i++) { int a=node[i].a,b=node[i].b; if(find(a)==find(b))continue; union(a,b);sum++;res+=node[i].w; } if(sum==n-1)System.out.println(res); else System.out.println("impossible"); } static void union(int a,int b){ a=find(a);b=find(b); p[a]=b; } static int find(int x){ if(x!=p[x]){ p[x]=find(p[x]); } return p[x]; } static class Node implements Comparable<Node>{ int a; int b; int w; public Node() {} public Node(int a, int b, int w) { this.a = a; this.b = b; this.w = w; } @Override public int compareTo(Node o) { // TODO Auto-generated method stub return w-o.w; } } }