spfa求最短路、spfa判断负环、Floyd求最短路、Kruskal算法求最小生成树

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输出样例2import 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 resInteger.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 nInteger.parseInt(g[0]),mInteger.parseInt(g[1]); Arrays.fill(h, -1); for (int i 0; i m; i) { gbr.readLine().split( ); int aInteger.parseInt(g[0]),bInteger.parseInt(g[1]),weInteger.parseInt(g[2]); add(a, b,we); } for (int i 2; i n; i) { d[i]Long.MAX_VALUE; } //bellman-ford的优化版 spfa QueueInteger queuenew LinkedListInteger(); queue.add(1);f[1]true; while(!queue.isEmpty()){ int pqueue.poll();f[p]false; for (int i h[p]; i!-1; ine[i]) { int je[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输出样例Yesimport 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 resInteger.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 nInteger.parseInt(g[0]),mInteger.parseInt(g[1]); Arrays.fill(h, -1); for (int i 0; i m; i) { gbr.readLine().split( ); int aInteger.parseInt(g[0]),bInteger.parseInt(g[1]),weInteger.parseInt(g[2]); add(a, b,we); } // 把所有点都入队那第一次更新的时候是哪些点被更新了呢 // 答案是负权边的入边那个点被更新了假设dt数组初始化为0那加上一个负边使得dt变小。所以如果要解释dt数组的含义的话假设图里不存在负权环那dt[i]的含义就是一个点走过有限次边到达i // 且走过的距离最小这个距离就是dt[i]。 //bellman-ford的优化版 spfa QueueInteger queuenew LinkedListInteger(); for (int i 1; i n; i) { queue.add(i);f[i]true; } while(!queue.isEmpty()){ int pqueue.poll();f[p]false; for (int i h[p]; i!-1; ine[i]) { int je[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≤n21≤m≤20000,图中涉及边长绝对值均不超过 10000。输入样例3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3输出样例impossible 1import 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 nInteger.parseInt(g[0]),mInteger.parseInt(g[1]),kkInteger.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) { gbr.readLine().split( ); int aInteger.parseInt(g[0]),bInteger.parseInt(g[1]),weInteger.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) { gbr.readLine().split( ); int xInteger.parseInt(g[0]),yInteger.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输出样例6import 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 nInteger.parseInt(g[0]),mInteger.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) { gbr.readLine().split( ); int aInteger.parseInt(g[0]),bInteger.parseInt(g[1]),weInteger.parseInt(g[2]); dis[a][b]Math.min(dis[a][b], we); dis[b][a]dis[a][b]; } int sum0;d[1]0; long res0; while(sumn){ int u-1; for (int i 1; i n; i) { if(f[i])continue; if(u-1 || d[u]d[i])ui; } if(d[u]Long.MAX_VALUE){ System.out.println(impossible); return; } f[u]true;sum; resd[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输出样例6import 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 nInteger.parseInt(g[0]),mInteger.parseInt(g[1]); for (int i 0; i m; i) { gbr.readLine().split( ); int aInteger.parseInt(g[0]),bInteger.parseInt(g[1]),weInteger.parseInt(g[2]); if(ab)continue; node[id]new Node(a, b, we); } for (int i 1; i n; i) { p[i]i; } Arrays.sort(node,0,id); int sum0;long res0; for (int i 0; i id sumn-1; i) { int anode[i].a,bnode[i].b; if(find(a)find(b))continue; union(a,b);sum;resnode[i].w; } if(sumn-1)System.out.println(res); else System.out.println(impossible); } static void union(int a,int b){ afind(a);bfind(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 ComparableNode{ 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; } } }