AcWing 1165. 单词环Java
原题链接
中等
作者:
季之秋
,
2021-05-19 18:06:36
,
所有人可见
,
阅读 250
import java.util.*;
public class Main{
static int N = 26*26+10, M = 100010, n;
static int e[] = new int[M], ne[] = new int[M], w[] = new int[M], h[] = new int[N], idx;
static double d[] = new double[N];
static int cnt[] = new int[N];
static boolean st[] = new boolean[N];
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);
for(int i = 0; i < n; i ++){
String s = sc.next();
int len = s.length();
if(len < 2) continue;
int left = (int)(s.charAt(0) - 'a') * 26 + (int)(s.charAt(1) - 'a');
int right = (int)(s.charAt(len-2) - 'a') * 26 + (int)(s.charAt(len-1) - 'a');
add(left, right, len);
}
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.println(r < 1e-4 ? "No solution" : r);
}
}
static boolean check(double mid){
Arrays.fill(st, true);
cnt = new int[N];
Queue<Integer> q = new LinkedList();
for(int i = 0; i < N; i ++){
q.add(i);
}
int count = 0;
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(d[j] < d[t] + w[i] - mid){
d[j] = d[t] + w[i] - mid;
if(count >= 5*N) return true; // 玄学优化 当时2*N的时候没过,就调成5*N然后A了
cnt[j] = cnt[t] + 1;
if(cnt[j] >= N) return true; // 超过点数,说明有些点走了两次了
if(!st[j]){
count ++;
st[j] = true;
q.add(j);
}
}
}
}
return false;
}
static void add(int a, int b, int c){
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++;
}
}