2024-01-31（最短路径）-CSDN博客
求负环的常用方法，基于spfa：
1.统计每个点入队的次数，如果有个点入队n次，则说明存在负环
2.统计当前每个点的最短路中包含的边数，如果某个点的最短路的所包含的边数大于等于 n，则说明也存在环
当所有点的入队次数大于2n时，我们就认为图中有很大的可能是存在负环的
(如果TLE了，那么可以把队列换成栈来试一下）
904. 虫洞 - AcWing题库
裸题
import java.util.*;
public class Main{
static int N = 510, M = 5500;
static int n, m1, m2, idx;
static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static int[] cnt = new int[M];//边数
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 spfa(){
Arrays.fill(dist, 0);
Arrays.fill(st, false);
Arrays.fill(cnt, 0);
Queue<Integer> q = new LinkedList<>();//循环队列
for(int i = 1; i <= n; i ++){//每个点入队
q.offer(i);
st[i] = true;
}
while(!q.isEmpty()){
int t = q.poll();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j]){
q.offer(j);
st[j] = true;
}
}
}
}
return false;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T -- > 0){
n = sc.nextInt();
m1 = sc.nextInt();
m2 = sc.nextInt();
Arrays.fill(h, -1);
idx = 0;//一定要记得！！！
while(m1 -- > 0){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);
add(b, a, c);
}
while(m2 -- > 0){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, -c);//虫洞的通道是单向的
}
if(spfa()) System.out.println("YES");
else System.out.println("NO");
}
}
}361. 观光奶牛 - AcWing题库
01分数规划：二分 -> 整理不等式 -> 重新定义边权 -> 判断图中是否存在正环
import java.util.*;
public class Main{
static int N = 1010, M = 5010;
static int n, m, idx;
static int[] wd = new int[N];//点权
static int[] h = new int[N], e = new int[M], ne = new int[M], wb = new int[M];//边权
static double[] dist = new double[N];
static int[] cnt = new int[N];
static boolean[] st = new boolean[N];
public static void add(int a, int b, int c){
e[idx] = b;
wb[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
public static boolean spfa(double x){
Arrays.fill(dist, 0);
Arrays.fill(st, false);
Arrays.fill(cnt, 0);
Queue<Integer> q = new LinkedList<>();
for(int i = 1; i <= n; i ++){
q.offer(i);
st[i] = true;
}
while(!q.isEmpty()){
int t = q.poll();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] < dist[t] + wd[t] - x * wb[i]){
dist[j] = dist[t] + wd[t] - x * wb[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j]){
q.offer(j);
st[j] = true;
}
}
}
}
return false;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);
for(int i = 1; i <= n; i ++){
wd[i] = sc.nextInt();
}
for(int i = 0; i < m; i ++){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);
}
//二分
double l = 0, r = 1010;
while(r - l > 1e-4){
double mid = (l + r) / 2;
if(spfa(mid)) l = mid;
else r = mid;
}
System.out.printf("%.2f", l);
}
}1165. 单词环 - AcWing题库
这道题就用到了前面说的技巧
import java.util.*;
public class Main{
static int N = 700, M = 100010;
static int n, idx;
static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
static int[] cnt = new int[N];
static boolean[] st = new boolean[N];
static double[] dist = new double[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(double x){
Arrays.fill(st, false);
Arrays.fill(dist, 0);
Arrays.fill(cnt, 0);
int count = 0;
Queue<Integer> q = new LinkedList<>();
for(int i = 0; i < 676; i ++){
q.offer(i);
st[i] = true;
}
while(!q.isEmpty()){
int t = q.poll();
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] < dist[t] + w[i] - x){
dist[j] = dist[t] + w[i] - x;
cnt[j] = cnt[t] + 1;
if(++ count > 10000) return true;
if(cnt[j] >= N) return true;
if(!st[j]){
q.offer(j);
st[j] = true;
}
}
}
}
return false;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(true){
n = sc.nextInt();
if(n == 0) break;
Arrays.fill(h, -1);
idx = 0;
for(int i = 0; i < n; i ++){
String str = sc.next();
int len = str.length();
if(len < 2) continue;
//转化为26进制数
int left = (str.charAt(0) - 'a') * 26 + (str.charAt(1) - 'a');
int right = (str.charAt(len - 2) - 'a') * 26 + (str.charAt(len - 1) - 'a');
add(left, right, len);
}
if(!check(0)){
System.out.println("No solution");
continue;
}
else{
double l = 0, r = 1000;
while(r - l > 1e-4){
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
System.out.printf("%.2f\n", r);
}
}
}
}
