树的重心、 图中点的层次、有向图的拓扑序列、Dijkstra求最短路 I、 有边数限制的最短路

树的重心给定一颗树树中包含 n 个结点编号 1∼n和 n−1 条无向边。请你找到树的重心并输出将重心删除后剩余各个连通块中点数的最大值。重心定义重心是指树中的一个结点如果将这个点删除后剩余各个连通块中点数的最大值最小那么这个节点被称为树的重心。输入格式第一行包含整数 n表示树的结点数。接下来 n−1 行每行包含两个整数 a 和 b表示点 a 和点 b 之间存在一条边。输出格式输出一个整数 m表示将重心删除后剩余各个连通块中点数的最大值。数据范围1≤n≤105输入样例9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6输出样例4import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N 2*100010,id,label-1; 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 p[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); Arrays.fill(h, -1);//1 for (int i 1; i n; i) { String g[]br.readLine().split( ); int aInteger.parseInt(g[0]),bInteger.parseInt(g[1]); add(a,b);add(b,a); } dfs(1,n,-1); System.out.println(res); } static long dfs(int root,int n,int p){ long sum0,sonmaxLong.MIN_VALUE; for (int i h[root]; i0; ine[i]) { int je[i]; if(jp)continue;//是父节点 跳过 long numdfs(j,n,root); sumnum; sonmaxMath.max(sonmax, num); } sonmaxMath.max(sonmax, n-sum-1); if(sonmaxres){ ressonmax; labelroot; } return sum1;//返回的是子树的总数 包含根 } static void add(int a,int b){ e[id]b; ne[id]h[a]; h[a]id; } }图中点的层次给定一个 n 个点 m 条边的有向图图中可能存在重边和自环。所有边的长度都是 1点的编号为 1∼n。请你求出 1 号点到 n 号点的最短距离如果从 1 号点无法走到 n 号点输出 −1。输入格式第一行包含两个整数 n 和 m。接下来 m 行每行包含两个整数 a 和 b表示存在一条从 a 走到 b 的长度为 1 的边。输出格式输出一个整数表示 1 号点到 n 号点的最短距离。数据范围1≤n,m≤105输入样例4 5 1 2 2 3 3 4 1 3 1 4输出样例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 2*100010,id,label-1; static long resInteger.MAX_VALUE; static int e[]new int[N]; static int ne[]new int[N]; static int h[]new int[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]); if(ab)continue; add(a,b); } Queuelong[] queuenew LinkedListlong[](); long r[]{1,0}; queue.add(r);f[1]true; while(!queue.isEmpty()){ long p[]queue.poll(); long nop[0],disp[1]; if(non){ System.out.println(dis); return; } for (int i h[(int)no]; i!-1; ine[i]) { int je[i]; if(jno)continue; if(f[j]true)continue; long t[]{j,dis1}; queue.add(t);f[j]true; } } System.out.println(-1); } static void add(int a,int b){ e[id]b; ne[id]h[a]; h[a]id; } }有向图的拓扑序列给定一个 n 个点 m 条边的有向图点的编号是 1 到 n图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列如果拓扑序列不存在则输出 −1。若一个由图中所有点构成的序列 A 满足对于图中的每条边 (x,y)x 在 A 中都出现在 y 之前则称 A 是该图的一个拓扑序列。输入格式第一行包含两个整数 n 和 m。接下来 m 行每行包含两个整数 x 和 y表示存在一条从点 x 到点 y 的有向边 (x,y)。输出格式共一行如果存在拓扑序列则输出任意一个合法的拓扑序列即可。否则输出 −1。数据范围1≤n,m≤105输入样例3 3 1 2 2 3 1 3输出样例1 2 3import 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 2*100010,id,label-1; static long resInteger.MAX_VALUE; static int e[]new int[N]; static int ne[]new int[N]; static int h[]new int[N]; static boolean f[]new boolean[N]; static int d[]new int[N];//存某一节点的入度 static long sum0; 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]); if(ab){ System.out.println(-1); return; } add(a,b);d[b]; } StringBuilder stringBuildernew StringBuilder(); QueueInteger queuenew LinkedList(); for (int i 1; i n; i) { if(d[i]0){ queue.add(i); stringBuilder.append(i ); f[i]true; sum; } } while(!queue.isEmpty()){ int rqueue.poll(); for (int i h[r]; i !-1; ine[i]) { int je[i]; if(f[j]true)continue; d[j]--; if(d[j]0){ stringBuilder.append(j );sum; queue.add(j);f[j]true; } } } if(sumn){ System.out.println(stringBuilder.toString()); }else{ System.out.println(-1); } } static int check(int n){ for (int i 1; i n; i) { if(f[i]true)continue; if(d[i]0)return i; } return -1; } static void add(int a,int b){ e[id]b; ne[id]h[a]; h[a]id; } }Dijkstra求最短路 I给定一个 n 个点 m 条边的有向图图中可能存在重边和自环所有边权均为正值。请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。输入格式第一行包含整数 n 和 m。接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。输出格式输出一个整数表示 1 号点到 n 号点的最短距离。如果路径不存在则输出 −1。数据范围1≤n≤500,1≤m≤105,图中涉及边长均不超过10000。输入样例3 3 1 2 2 2 3 1 1 3 4输出样例3邻接表import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; public class Main { static int N 100010,id; static long resInteger.MAX_VALUE; static int e[]new int[N]; static int w[]new int[N]; static int ne[]new int[N]; static int h[]new int[N]; static boolean f[]new boolean[N]; static long d[]new long[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]),weightInteger.parseInt(g[2]); if(ab){ continue; } add(a,b,weight); } d[1]0; for (int i 2; i n; i) { d[i]Long.MAX_VALUE; } Dijkstra(1,n); } static void Dijkstra(int b,int end){ PriorityQueueNode priorityQueuenew PriorityQueue(); priorityQueue.add(new Node(b,0)); while(!priorityQueue.isEmpty()){ Node nopriorityQueue.poll();f[b]true; int pno.dian;long disno.dis; if(pend){ System.out.println(dis); return; } for (int i h[p]; i ! -1; ine[i]) { int je[i]; if(f[j]true)continue; if(d[j]d[p]w[i]){ d[j]d[p]w[i]; priorityQueue.add(new Node(j,d[j])); } } } System.out.println(-1); } static class Node implements ComparableNode{ int dian; long dis; public Node() { // TODO Auto-generated constructor stub } public Node(int dian, long dis) { this.dian dian; this.dis dis; } Override public int compareTo(Node o) { // TODO Auto-generated method stub return this.dis-o.dis0?1:-1; } } static void add(int a,int b,int weight){ e[id]b;w[id]weight; ne[id]h[a]; h[a]id; } }邻接矩阵import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N 510,id; static boolean f[]new boolean[N]; static long d[]new long[N]; static int e[][]new int[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]); for (int i 1; i n; i) { Arrays.fill(e[i], Integer.MAX_VALUE); e[i][i]0; } for (int i 0; i m; i) { gbr.readLine().split( ); int aInteger.parseInt(g[0]),bInteger.parseInt(g[1]),weightInteger.parseInt(g[2]); if(ab){ continue; } e[a][b]Math.min(e[a][b], weight); } d[1]0; for (int i 2; i n; i) { d[i]Integer.MAX_VALUE; } for (int i 0; i n-1; i) { int t-1; for (int j 1; j n; j) { if(f[j]true)continue; if(t-1 || d[t]d[j])tj; } if(t-1){ System.out.println(-1); return; } f[t]true; for (int j 1; j n; j) { if(jt)continue; if(e[t][j]!Integer.MAX_VALUE){ d[j]Math.min(d[j], d[t]e[t][j]); } } } if(d[n]!Integer.MAX_VALUE){ System.out.println(d[n]); }else{ System.out.println(-1); } } }有边数限制的最短路给定一个 n 个点 m 条边的有向图图中可能存在重边和自环边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离如果无法从 1 号点走到 n 号点输出impossible。注意图中可能存在负权回路。输入格式第一行包含三个整数 n,m,k。接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。点的编号为 1∼n。输出格式输出一个整数表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。如果不存在满足条件的路径则输出impossible。数据范围1≤n,k≤500,1≤m≤10000,1≤x,y≤n任意边长的绝对值不超过 10000。输入样例3 3 1 1 2 1 2 3 1 1 3 3输出样例3import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N 10010,id; static long resInteger.MAX_VALUE; static Edge edges[]new Edge[N]; static long d[]new long[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]),kInteger.parseInt(g[2]); for (int i 0; i m; i) { gbr.readLine().split( ); int aInteger.parseInt(g[0]),bInteger.parseInt(g[1]),wInteger.parseInt(g[2]); edges[id]new Edge(a, b, w); } d[1]0; for (int i 2; i n; i) { d[i]Long.MAX_VALUE; } for (int i 0; i k; i) { long dd[]Arrays.copyOfRange(d, 0, n1);//下面在更新的时候 必须使用上一轮的d 使用本轮的d可能会使得边数超过k for (int j 0; j id; j) { int aedges[j].a,bedges[j].b,wedges[j].w; if(d[b]Long.MAX_VALUE){ if(dd[a]!Long.MAX_VALUE) d[b] dd[a]w; }else{ if(dd[a]!Long.MAX_VALUE) d[b]Math.min(d[b], dd[a]w); } } } // for (int i 1; i n; i) { // System.out.println(d[i]); // } if(d[n]Long.MAX_VALUE){ System.out.println(impossible); }else{ System.out.println(d[n]); } } static class Edge{ int a; int b; int w; public Edge() { // TODO Auto-generated constructor stub } public Edge(int a, int b, int w) { this.a a; this.b b; this.w w; } } }