2024蓝桥杯赛前模版突击:图论篇
图论在蓝桥杯中一般考的不难,如果有图论的题,就基本是模板题,知道板子就有分了。
邻接表
本文使用方法1的方式实现邻接表
邻接表1
static int[] dist = new int[N],st = new int[N];
static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];
static int idx;
static void init(){
Arrays.fill(h,-1);
}
static void add(int a,int b,int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
邻接表2
用来快速得到顶点的所有邻边条数
leetcode中比较常见
ArrayList[] g = new ArrayList[N];
//初始化
for(int i=0;i();
//顶点a,b中间添加一条边
g[a].add(b);
最短路Dijkstra
单源最短路 O(mlogn)
package _00模板;
import java.util.*;
public class Dijkstra {
static int INF = 0x3f3f3f3f;
static int N = 101000,M = 2*N;
static int[] dist = new int[N],st = new int[N];
static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];
static int idx;
static int n,m;
static long ans;
static void add(int a,int b,int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
static int dijkstra(int start) {
Arrays.fill(dist,INF);
PriorityQueue q = new PriorityQueue((a,b)->a.dist-b.dist);
q.add(new PII(start,0));
st[start] = 0;
while(q.size()>0) {
PII top = q.poll();
if (st[top.v]==1) continue;
st[top.v] = 1;
for(int i=h[top.v];i!=-1;i=ne[i]) {
int j = e[i],val = w[i];
if(dist[top.v]+val
最短路spfa
负权图的最短路O(m*n)
package _00模板;
import java.util.*;
public class Spfa {
static int INF = 0x3f3f3f3f;
static int N = 101000,M = 2*N;
static int[] st = new int[N],dist = new int[N];
static int n,m;
static long ans;
static int[] h = new int[N],e = new int[M],w = new int[M],ne = new int[M];
static int idx;
static void add(int a,int b,int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
static int spfa(int start) {
Arrays.fill(dist,INF);
Queue q = new LinkedList();
q.add(start);
st[start] = 1;
dist[start] = 0;
while(q.size()>0) {
int top = q.poll();
st[top] = 0;
for(int i=h[top];i!=-1;i=ne[i]) {
int j = e[i];
if(dist[top]+w[i]
Floyd
多源最短路O(n^3)
package _00模板;
import java.util.*;
public class Floyd {
static int INF = 0x3f3f3f3f;
static int N = 101000,M = 2*N;
static int[][] g服务器托管 = new int[N][N];
static int n,m;
static long ans;
static void floyd() {
for(int k=1;k
最小生成树kruskal
kruskal 算法O (mlogm服务器托管),Prim不需要掌握,用kruskal 就行
package _00模板;
import java.util.*;
public class Kruskal {
static int INF = 0x3f3f3f3f;
static int N = 101000,M = 2*N;
static Edge[] edges = new Edge[N];
static int idx;
static int n,m;
static long ans;
static int[] fa = new int[N];
static void init() {
for(int i=1;i(a.w-b.w));
int cnt = 0,res = 0;
for(int i=0;i
拓扑排序
int[] d = new int[N];//存放入度
int[] print = new int[N];//记录答案
int cnt;
static boolean topSort() {
Queue q = new LinkedList();
for(int i=1;i0) {
Integer top = q.poll();
print[cnt++] = top;
for(int i=h[top];i!=-1;i=ne[i]) {
int j = e[i];
d[j]--;
if(d[j]==0) {
q.add(j);
}
}
}
return n==cnt;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i=1;i
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net