头像

小崔崔

是她




离线:13小时前


最近来访(215)
用户头像
Colopen
用户头像
似近似远
用户头像
Tilbur
用户头像
Nottoday
用户头像
15084948533
用户头像
sketch
用户头像
Aaron_8
用户头像
凌乱之风
用户头像
智村长
用户头像
QAQlzy
用户头像
曹大碧
用户头像
utt
用户头像
小猫咪能有什么坏心眼呢
用户头像
胃疼的007
用户头像
yuxi
用户头像
wslwlm
用户头像
心向远方
用户头像
NBxiang
用户头像
算法小爱
用户头像
Hustle

活动打卡代码 AcWing 1165. 单词环

小崔崔
20小时前
import java.util.*;
public class Main {
    static int N = 700, M = 100010;

    static int ne[] = new int[M], w[] = new int[M], to[] = 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];

    static void add(int a, int b, int c) {
        w[idx] = c; to[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
    }

    static boolean check(double mid) {
        Arrays.fill(cnt, 0);
        Arrays.fill(d, 0);
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < N; i ++ ) {
            q.add(i);
            st[i] = true;
        }

        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 = to[i];
                if(d[j] < d[t] + w[i] - mid) {
                    d[j] = d[t] + w[i] - mid;
                    cnt[j] = cnt[t] + 1;

                    if( ++ count > 5 * N) return true;
                    if(cnt[j] >= N) return true;

                    if(!st[j]) {
                        st[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while(n != 0) {
            Arrays.fill(h, -1);
            idx = 0;
            for(int i = 0; i < n; i ++ ) {
                char cs[] = sc.next().toCharArray();
                int len = cs.length;
                int a = (cs[0] - 'a') * 26 + (cs[1] - 'a');
                int b = (cs[len - 2] - 'a') * 26 + (cs[len - 1] - 'a');
                add(a, b, len);
            }

            if(!check(0)) System.out.println("No solution");
            else {
                double l = 0, r = 1000;
                while(r - l > 1e-5) {
                    double mid = (l + r) / 2;
                    if(check(mid))
                        l = mid;
                    else
                        r = mid;
                }
                System.out.println(l);
            }


            n = sc.nextInt();
        }
    }

}


活动打卡代码 AcWing 904. 虫洞

小崔崔
20小时前
import java.util.*;
public class Main {
    static int N = 510, M = 5500;

    static int w[] = new int[M], h[] = new int[N], ne[] = new int[M], to[] = new int[M], idx;  
    static boolean st[] = new boolean[N];
    static int dist[] = new int[N], cnt[] = new int[N];
    static int n, m1, m2;

    static void add(int a, int b, int c) {
        w[idx] = c; to[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
    }

    static boolean spfa() {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= n; i ++ ) {
            q.offer(i);
            st[i] = true;
            cnt[i] = dist[i] = 0;
        }

        while(!q.isEmpty()) {
            int v = q.poll();
            st[v] = false;

            for(int i = h[v]; i != -1; i = ne[i]) {
                int j = to[i];
                if(dist[j] > dist[v] + w[i]) {
                    dist[j] = dist[v] + w[i];
                    cnt[j] = cnt[v] + 1;

                    if(cnt[j] >= n)
                        return true;

                    if(!st[j]) {
                        st[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
        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;

            for(int i = 0; i < m1; i ++ ) {
                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 < m2; i ++ ) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int c = sc.nextInt();
                add(a, b, -c);
            }

            String res = spfa() ? "YES" : "NO";
            System.out.println(res);
        }
    }

}


活动打卡代码 AcWing 361. 观光奶牛

import java.util.*;
public class Main {
    static int N = 1010, M = 5010;

    static int to[] = new int[M], ne[] = new int[M], h[] = new int[N], w[] = new int[M], idx;
    static int cnt[] = new int[N], wf[] = new int[N];
    static double dist[] = new double[N];
    static boolean st[] = new boolean[N];
    static int n, m;

    static void add(int a, int b, int c) {
        w[idx] = c; to[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
    }

    static boolean check(double mid) {
        Arrays.fill(dist, 0);
        Arrays.fill(cnt, 0);
        Arrays.fill(st, false);
        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 = to[i];
                if(dist[j] < dist[t] + wf[t] - mid * w[i]) {
                    dist[j] = dist[t] + wf[t] - mid * w[i];
                    cnt[j] = cnt[t] + 1;

                    if(cnt[j] >= n)
                        return true;
                    if(!st[j]) {
                        st[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1; i <= n; i ++ ) wf[i] = 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);
        }

        double l = 0, r = 1010;
        while(r - l > 1e-4) {
            double mid = (r + l) / 2;
            if(check(mid)) l = mid;
            else r = mid;
        }

        System.out.printf("%.2f", l);
    }
}



import java.util.*;
public class Main {
    static class e implements Comparable<e> {
        int a, b, d;
        boolean is = false;
        public e(int aa, int bb, int cc) {
            a = aa; b = bb; d = cc;
        }
        public int compareTo(e o) {
            return this.d - o.d;
        }
    }

    static int N = 510, M = 10010;

    static int n, m;
    static int p[] = new int[N];
    static e es[] = new e[M];
    static int max1[][] = new int[N][N], max2[][] = new int[N][N];
    static int ne[] = new int[N * 2], to[] = new int[N * 2], w[] = new int[N * 2], h[] = new int[N], idx;

    static int find(int x) {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static void add(int a, int b, int c) {
        w[idx] = c; to[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
    }

    static void dfs(int u, int m1, int m2, int fa, int cur) {
        max1[cur][u] = m1;
        max2[cur][u] = m2;

        for(int i = h[u]; i != -1; i = ne[i]) {
            int j = to[i];
            if(j == fa) continue;
            int t1 = m1, t2 = m2;
            if(w[i] > m1) {
                m2 = m1;
                m1 = w[i];
            }else if(w[i] < m1 && w[i] > m2) {
                m2 = w[i];
            }
            dfs(j, m1, m2, u, cur);
            m1 = t1; m2 = t2;
        }
    }



    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 = 0; i < m; i ++ ) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            es[i] = new e(a, b, c);
        }

        Arrays.sort(es, 0, m);
        for(int i = 1; i <= n; i ++ ) p[i] = i;

        long sum = 0;
        for(int i = 0; i < m; i ++ ) {
            int a = find(es[i].a), b = find(es[i].b);
            if(a != b) {
                p[a] = b;
                sum += es[i].d;
                es[i].is = true;
                add(es[i].a, es[i].b, es[i].d);
                add(es[i].b, es[i].a, es[i].d);
            }
        }

        for(int i = 1; i <= n; i ++ ) {
            dfs(i, 0, 0, -1, i);
        }

        long res = (long)1e18;
        for(int i = 0; i < m; i ++ ) {
            if(!es[i].is) {
                int a = es[i].a, b = es[i].b, w = es[i].d;
                if(w > max1[a][b]) {
                    res = Math.min(res, sum - max1[a][b] + w);
                }else if(w == max1[a][b] && w  > max2[a][b]) {
                    res = Math.min(res, sum - max2[a][b] + w);
                }

            }
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 346. 走廊泼水节

import java.util.*;
public class Main {
    static class e implements Comparable<e> {
        int a, b, d;
        public e(int aa, int bb, int cc) {
            a = aa; b = bb; d = cc;
        }
        public int compareTo(e o) {
            return this.d - o.d;
        }
    }

    static int N = 6010;
    static e es[] = new e[N];
    static int p[] = new int[N], size[] = new int[N];

    static int find(int x) {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        while(T -- > 0) {
            int n = sc.nextInt();
            for(int i = 0; i < n - 1; i ++ ) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int c = sc.nextInt();
                es[i] = new e(a, b, c);
            }

            Arrays.sort(es, 0, n - 1);

            for(int i = 1; i <= n; i ++ ) {
                p[i] = i; size[i] = 1;
            }

            int res = 0;
            for(int i = 0; i < n - 1; i ++ ) {
                int a = find(es[i].a), b = find(es[i].b), w = es[i].d;
                if(a != b) {
                    res += (size[a] * size[b] - 1) * (w + 1);
                    p[a] = b;
                    size[b] += size[a];
                }
            }

            System.out.println(res);
        }
    }
}


活动打卡代码 AcWing 1145. 北极通讯网络

// 16:34
import java.util.*;
public class Main {
    static class e implements Comparable<e> {
        int a, b;
        double d;
        public int compareTo(e o) {
            return (int)(this.d - o.d);
        }
    }

    static int N = 510;

    static e es[] = new e[N * N];
    static int xs[] = new int[N], ys[] = new int[N];
    static int p[] = new int[N];
    static int n, k;

    static int init() {
        int t = 0;
        for(int i = 1; i <= n; i ++ )
            for(int j = i + 1; j <= n; j ++ , t ++ ) {
                es[t] = new e();
                es[t].a = i; es[t].b = j; es[t].d = get(i, j);
            }
        return t;
    }

    static double get(int a, int b) {
        double t1 = xs[a] - xs[b];
        double t2 = ys[a] - ys[b];
        return Math.sqrt(t1 * t1 + t2 * t2);
    }

    static int find(int x) {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        for(int i = 1; i <= n; i ++ ) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            xs[i] = a; ys[i] = b;
            p[i] = i;
        }

        int m = init();
        Arrays.sort(es, 0, m);

        int liantong = n;
        double res = 0;
        for(int i = 0; i < m && liantong > k; i ++ ) {
            int a = find(es[i].a);
            int b = find(es[i].b);
            if(a != b) {
                res = es[i].d;
                liantong -- ;
                p[a] = b;
            }
        }

        System.out.printf("%.2f",res);
    }
}


活动打卡代码 AcWing 1146. 新的开始

import java.util.*;
public class Main {
    static int N = 310;

    static int g[][] = new int[N][N];
    static int d[] = new int[N];
    static boolean st[] = new boolean[N];
    static int n;

    static int prim() {
        Arrays.fill(d, 10000000);
        int res = 0;

        for(int i = 0; i <= n; i ++ ) {
            int t = -1;
            for(int j = 0; j <= n; j ++ )
                if(!st[j] && (t == -1 || d[j] < d[t]))
                    t = j;

            st[t] = true;
            if(i != 0) res += d[t];

            for(int j = 0; j <= n; j ++ ) 
                d[j] = Math.min(d[j], g[j][t]);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        for(int i = 1; i <= n; i ++ ) {
            g[i][0] = sc.nextInt();
            g[0][i] = g[i][0];
        }
        for(int i = 1; i <= n; i ++ ) 
            for(int j = 1; j <= n; j ++ )
                g[i][j] = sc.nextInt();

        System.out.println(prim());
    }
}


活动打卡代码 AcWing 1144. 连接格点


import java.util.*;
public class Main {
    static class e {
        int a, b, d;
        public e(int aa, int bb, int cc) {
            a = aa; b = bb; d = cc;
        }
    }

    static int N = 1010;

    static int p[] = new int[N * N];
    static int ids[][] = new int[N][N];
    static e es[] = new e[2 * N * N];
    static int n, m;

    static int find(int x) {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static int get_edges() {
        int cnt = 0;
        for(int j = 1; j <= m; j ++ ) {
            for(int i = 1; i <= n - 1; i ++ ) {
                int a = ids[i][j], b = ids[i + 1][j];
                es[cnt ++ ] = new e(a, b, 1);
            }
        }

        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= m - 1; j ++ ) {
                int a = ids[i][j], b = ids[i][j + 1];
                es[cnt ++ ] = new e(a, b, 2);
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for(int i = 1, t = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ ) {
                ids[i][j] = t ++ ;
            }

        for(int i = 1; i < N * N; i ++ ) p[i] = i;

        while(sc.hasNext()) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            int a = ids[x1][y1], b = ids[x2][y2];
            p[find(a)] = find(b);
        }

        int res = 0;
        int cnt = get_edges();
        for(int i = 0; i < cnt; i ++ ) {
            int a = find(es[i].a);
            int b = find(es[i].b);
            if(a != b) {
                p[a] = b;
                res += es[i].d;
            }
        }

        System.out.println(res);
    }

}


活动打卡代码 AcWing 1143. 联络员

import java.util.*;
public class Main {
    static class e implements Comparable<e> {
        int a, b, d;
        public e(int aa, int bb, int cc) {
            a = aa; b = bb; d = cc;
        }
        public int compareTo(e o) {
            return this.d - o.d;
        }
    }

    static int N = 2010, M = 10010;

    static int p[] = new int[N];
    static e es[] = new e[M];
    static int n, m;

    static int find(int x) {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int q = 0, res = 0;

        for(int i = 1; i <= n; i ++ ) p[i] = i;

        for(int i = 0; i < m; i ++ ) {
            int pp = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            if(pp == 1) {
               a = find(a); b = find(b);
               p[a] = b;
               res += c;
            }else
                es[q ++ ] = new e(a, b, c);
        }

        Arrays.sort(es, 0, q);

        for(int i = 0; i < q; i ++ ) {
            int a = find(es[i].a);
            int b = find(es[i].b);

            if(a != b) {
                p[a] = b;
                res += es[i].d;
            }
        }

        System.out.println(res);
    }

}


活动打卡代码 AcWing 1142. 繁忙的都市

import java.util.*;
public class Main {
    static class e implements Comparable<e> {
        int d, a, b;
        public e(int aa, int bb, int cc) {
            a = aa; b = bb; d = cc;
        }
        public int compareTo(e o){
            return this.d - o.d;
        }
    }

    static int N = 310;

    static e es[] = new e[9000];
    static int n, m;
    static int p[] = new int[N];

    static int find(int x) {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static boolean check(int x) {
        for(int i = 1; i <= n; i ++ )
            p[i] = i;

        int sum = 0;
        for(int i = 0; i < m; i ++ ) {
            int a = es[i].a;
            int b = es[i].b;
            int d = es[i].d;

            if(d > x) break;

            a = find(a); b = find(b);
            if(a != b) {
                p[a] = b;
                sum ++ ;
            }
        }

        return sum == n - 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         n = sc.nextInt();
         m = sc.nextInt();

         for(int i = 0; i < m; i ++ ) {
             int a = sc.nextInt();
             int b = sc.nextInt();
             int c = sc.nextInt();
             es[i] = new e(a, b, c);
         }

         Arrays.sort(es, 0, m);

         int l = 1, r = 10000;
         while(l < r) {
             int mid = l + r >> 1;
             if(check(mid))
                r = mid;
            else
                l = mid + 1;
         }
         System.out.println(n - 1 + " " + l);
    }

}