1135. 新年好 - AcWing题库
单源最短路和暴搜的结合
import java.util.*;
class PII implements Comparable<PII>{
int num, distance;
public PII(int num, int distance){
this.num = num;
this.distance = distance;
}
public int compareTo(PII o){
return distance - o.distance;
}
}
public class Main{
static int N = 50010, M = 100010 * 2, idx, n, m, INF = 0x3f3f3f3f;
static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
static boolean[] st = new boolean[N];
static int[][] dist = new int[6][N];
static int[] source = new int[6];
//邻接表存储
public static void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
//打表，预处理
public static void dijkstra(int u, int[] dist){
PriorityQueue<PII> q = new PriorityQueue<>();
Arrays.fill(st, false);
Arrays.fill(dist, INF);
q.offer(new PII(u, 0));
dist[u] = 0;
while(!q.isEmpty()){
PII t = q.poll();
int distance = t.distance;
int num = t.num;
if(st[num]) continue;//遍历过
st[num] = true;//进行标记
for(int i = h[num]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > distance + w[i]){
dist[j] = distance + w[i];
q.offer(new PII(j, dist[j]));
}
}
}
}
public static int dfs(int u, int start, int distance){
if(u == 6) return distance;
int res = INF;
//枚举五个亲戚
for(int i = 1; i <= 5; i ++){
if(!st[i]){
int next = source[i];//取出亲戚的编号
st[i] = true;//标记为已用过
res = Math.min(res, dfs(u + 1, i, distance + dist[start][next]));//从表中查询
st[i] = false;//恢复现场
}
}
return res;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);//初始化表头
source[0] = 1;
for(int i = 1; i <= 5; i ++){
source[i] = sc.nextInt();
}
while(m -- > 0){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);
add(b, a, c);
}
for(int i = 0; i < 6; i ++){
dijkstra(source[i], dist[i]);
}
Arrays.fill(st, false);
System.out.print(dfs(1, 0, 0));//第一个位置，以第几个点为起点，当前距离之和
}
}
340. 通信线路 - AcWing题库
单源最短路和二分的结合。本质上是求最大值最小，联想到二分法来求
二分思路：
定义在[0, 1000001]这个区间中x的划分符合以下性质：
从1到n，最少经过的长度大于x的边的数量是否小于等于k。
AcWing 340. 通信线路 - AcWing
import java.util.*;
public class Main{
static int N = 1010, M = 10010 * 2, INF = 0x3f3f3f3f;
static int n, m, k, idx;
static int[] h = new int[N], ne = new int[M], e = new int[M], w = new int[M];
static boolean[] st = new boolean[N];
static Deque<Integer> q = new LinkedList<>();//双端队列
static int[] dist = new int[N];
//邻接表存储
public static void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
public static boolean check(int x){
Arrays.fill(st, false);//有多组数据，每一次都要进行初始化
Arrays.fill(dist, INF);
dist[1] = 0;
q.addLast(1);
while(!q.isEmpty()){
int t = q.pollFirst();
if(st[t]) continue;
st[t] = true;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
int v = w[i] > x ? 1 : 0;
if(dist[j] > dist[t] + v){
dist[j] = dist[t] + v;
if(v == 0) q.addFirst(j);
else q.addLast(j);
}
}
}
return dist[n] <= k;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
Arrays.fill(h, -1);//初始化队头
while(m -- > 0){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);//无向图
add(b, a, c);
}
//二分
int l = 0, r = (int)1e6 + 1;
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(r == 1e6 + 1) r = -1;
System.out.print(r);
}
}
342. 道路与航线 - AcWing题库
拓扑排序和dijkstra相结合
2024-01-30(树与图的深度优先遍历、广度优先遍历、拓扑排序）-CSDN博客
/***
* 1.首先输入双向道路，然后将他们分块，用dfs求出所有的连通块，用id[]存这些点所在的
* 连通块的编号，用block[]存这个连通块中有哪些点
* 2.然后输入单向航线，将所有连通块的入度统计出来
* 3.将所有的距离初始化为INF，起点S初始化为0，进行拓扑排序，在topsort函数中，将所有
* 入度是0的连通块加入到队列当中，然后每次弹出队首的编号t，将这个t进行dijkstra
* 4.在dijkstra中，创建一个优先队列（小根堆）将这个连通块中所有的点都加入到优先队列
* 中，每次弹出的队首是一个PII（distance，num），如果已经标记过就continue，否则就
* 标记为true，枚举它的所有出边，如果dist[j] > distance + w[i]，那么进行更新。然后
* 判断一下，如果id[j]和id[num]两个点是一样的说明在同一个连通块中，那么加入优先队列
* 如果id[j]!=id[num]那么说明是单项航线，那么将这个点j所对应的连通块的入度减1，当
* 这个连通块的入度为0的时候，就把它加入到全局变量中去
**/
import java.util.*;
import java.io.*;
class PII implements Comparable<PII>{
int distance, num;
public PII(int distance, int num){
this.distance = distance;
this.num = num;
}
public int compareTo(PII o){
return distance - o.distance;
}
}
public class Main{
static int N = 25010, M = 150010, INF = 0x3f3f3f3f;
//n表示所有的点，mr表示双向道路，mp表示单项航线，S表示起点，cnt表示连通块的编号
static int n, mr, mp, idx, S, cnt;
static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
static boolean[] st = new boolean[N];
static Queue<Integer> q = new LinkedList<>();
static int[] id = new int[N];//这个点属于哪个连通块
static List<Integer>[] block = new ArrayList[N];//这个连通块中有哪些点
static int[] din = new int[N];//连通块的入度
static int[] dist = new int[N];//距离
//邻接表存储
public static void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
//u表示点的编号，cnt表示连通块的编号
public static void dfs(int u, int cnt){
id[u] = cnt;
//如果这个连通块还没有，那么就建立一个新的block
if(block[cnt] == null) block[cnt] = new ArrayList<>();
block[cnt].add(u);//把这个点加入到这个连通块中
//遍历这个点的所有邻接点
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
//这个邻接点所属的连通块的编号为0，也就是说还没有进行分配，那么进行dfs
if(id[j] == 0) dfs(j, cnt);
}
}
public static void topsort(){
Arrays.fill(dist, INF);
dist[S] = 0;
//所有入度为0的连通块加入队列
for(int i = 1; i <= cnt; i ++){
if(din[i] == 0) q.offer(i);
}
while(!q.isEmpty()){
int t = q.poll();
dijkstra(t);//t表示连通块的编号
}
}
//堆优化版的dijkstra算法
public static void dijkstra(int bid){//bid表示连通块的编号
PriorityQueue<PII> queue = new PriorityQueue<>();//优先队列
//循环遍历这个连通块里的所有点，并把它们加入优先队列中
for(int ver : block[bid]) queue.offer(new PII(dist[ver], ver));
while(queue.size() != 0){
PII t = queue.poll();//取出队头
int num = t.num;
int distance = t.distance;
if(st[num]) continue;
st[num] = true;
for(int i = h[num]; i != -1; i = ne[i]){
int j = e[i];
//判断不属于一个连通块
if(id[j] != id[num] && -- din[id[j]] == 0) q.offer(id[j]);
if(dist[j] > distance + w[i]){
dist[j] = distance + w[i];
//判断一下是否同属于一个连通块
if(id[j] == id[num]) queue.offer(new PII(dist[j], j));
}
}
}
}
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
mr = Integer.parseInt(s[1]);
mp = Integer.parseInt(s[2]);
S = Integer.parseInt(s[3]);
Arrays.fill(h, -1);//初始化队头
//输入双向航线
while(mr -- > 0){
String[] arr = br.readLine().split(" ");
int a = Integer.parseInt(arr[0]);
int b = Integer.parseInt(arr[1]);
int c = Integer.parseInt(arr[2]);
add(a, b, c);
add(b, a, c);
}
//找出所有点所属的连通块，并且每个连通块中有哪些点
for(int i = 1; i <= n; i ++){
//如果这个点还没有找到所属的连通块，那么说明它属于另一个连通块，所以连通块的编号要加1
if(id[i] == 0) dfs(i, ++ cnt);
}
//接下来读入单向航线
while(mp -- > 0){
String[] str = br.readLine().split(" ");
int a = Integer.parseInt(str[0]);
int b = Integer.parseInt(str[1]);
int c = Integer.parseInt(str[2]);
add(a, b, c);
din[id[b]] ++;//将编号为b的点所属的连通块的入度加1
}
//开始进行拓扑排序
topsort();
for(int i = 1; i <= n; i ++){
if(dist[i] > INF / 2) System.out.println("NO PATH");
else System.out.println(dist[i]);
}
}
}
341. 最优贸易 - AcWing题库
单源最短路和dp的结合
dp问题绝大部分上是拓扑图上的最短（最长）路径问题
AcWing 341. 最优贸易 - AcWing
import java.util.*;
import java.io.*;
public class Main{
//这里M取这个值是因为最坏的情况下都是无向边，我们还要建立反向图
static int N = 100010, M = 2000010, INF = 0x3f3f3f3f;
static int n, m, idx;
static int[] hl = new int[N], hr = new int[N], e = new int[M], ne = new int[M];
static int[] w = new int[N];//点的权重
static int[] dmin = new int[N], dmax = new int[N];
static boolean[] st = new boolean[N];
public static void add(int[] h, int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
public static void spfa(int[] h, int[] dist, int type){
Queue<Integer> q = new LinkedList<>();//循环队列
if(type == 0){
//求最小值
Arrays.fill(dist, INF);
dist[1] = w[1];
q.offer(1);
}else{
//求最大值
Arrays.fill(dist, -INF);
dist[n] = w[n];
q.offer(n);
}
while(!q.isEmpty()){
int t = q.poll();
st[t] = false;//取出队头，st置为false
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if((type == 0 && dist[j] > Math.min(dist[t], w[j])) || (type == 1 && dist[j] < Math.max(dist[t], w[j]))){
if(type == 0) dist[j] = Math.min(dist[t], w[j]);
else dist[j] = Math.max(dist[t], w[j]);
if(!st[j]){
q.offer(j);
st[j] = true;
}
}
}
}
}
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
Arrays.fill(hl, -1);//初始化队头
Arrays.fill(hr, -1);//初始化反向队头
String[] arr = br.readLine().split(" ");
for(int i = 1; i <= n; i ++){
w[i] = Integer.parseInt(arr[i - 1]);
}
//建图
for(int i = 1; i <= m; i ++){
String[] str = br.readLine().split(" ");
int a = Integer.parseInt(str[0]);
int b = Integer.parseInt(str[1]);
int c = Integer.parseInt(str[2]);
add(hl, a, b);
add(hr, b, a);
if(c == 2){//双向道路
add(hr, a, b);
add(hl, b, a);
}
}
//求最大值是1，最小值是0
spfa(hl, dmin, 0);
spfa(hr, dmax, 1);
int res = 0;
for(int i = 1; i <= n; i ++){//以i为分界点
res = Math.max(res, dmax[i] - dmin[i]);
}
System.out.print(res);
}
}
