头像

Zycccc

$\color{#FFD700}{上方山骇客协会}$




在线 


最近来访(162)
用户头像
猫君勉乎哉
用户头像
Java同学
用户头像
铜翌
用户头像
羽佳
用户头像
扇贝_6
用户头像
yxc
用户头像
zhangyuzhe
用户头像
华科
用户头像
济带阿孙
用户头像
jaylenwanghitsz
用户头像
skydegree
用户头像
瑜huang
用户头像
我记得住
用户头像
JcWing
用户头像
Fatin
用户头像
小郑同学
用户头像
绿的精神
用户头像
SH_8
用户头像
AAAL
用户头像
bigbig麻瓜


Zycccc
2小时前
import java.io.*;
import java.util.*;

class Edge {
    int a, b, w;
    public Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
}
public class Main {
    static final int N = 200010;
    static int n, m;
    static int u, v, w;
    static int[] p = new int[N];
    static Edge[] edge = new Edge[N];
    static int find(int x) {
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    static int Kruskal() {
        int res = 0;
        int cnt = 0;
        Arrays.sort(edge, 0, m, (a, b)->{return a.w - b.w;});
        for (int i = 0; i < m; i++) {
            Edge e = edge[i];
            int a = e.a;
            int b = e.b;
            int w = e.w;
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                res += w;
                cnt++;
            }
        }
        if (cnt < n - 1) return 0x3f3f3f3f;
        return res;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first_line = br.readLine().split(" ");
        n = Integer.parseInt(first_line[0]);
        m = Integer.parseInt(first_line[1]);
        for (int i = 1; i <= n; i++) p[i] = i;
        for (int i = 0; i < m; i++) {
            String[] second_line = br.readLine().split(" ");
            u = Integer.parseInt(second_line[0]);
            v = Integer.parseInt(second_line[1]);
            w = Integer.parseInt(second_line[2]);
            edge[i] = new Edge(u, v, w);
        }
        int ans = Kruskal();
        if (ans == 0x3f3f3f3f) {
            bw.write("impossible\n");
            bw.flush();
        }
        else {
            bw.write(ans + "\n");
            bw.flush();
        }
    }
}



Zycccc
2小时前
import java.io.*;
import java.util.*;

public class Main {
    static final int N = 200010;
    static int n, m, idx;
    static int u, v;
    static int[] e = new int[N], ne = new int[N], h = new int[N], color = new int[N];
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static boolean dfs(int u, int c) {
        color[u] = c;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (color[j] == 0) {
                if (!dfs(j, 3 - c)) return false;
            }
            else if (color[j] == c) return false;
        }
        return true;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Arrays.fill(h, -1);
        String[] first_line = br.readLine().split(" ");
        n = Integer.parseInt(first_line[0]);
        m = Integer.parseInt(first_line[1]);
        while (m-- != 0) {
            String[] second_line = br.readLine().split(" ");
            u = Integer.parseInt(second_line[0]);
            v = Integer.parseInt(second_line[1]);
            add(u, v);
            add(v, u);
        }
        boolean flag = true;
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0 && !dfs(i, 1)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            bw.write("Yes\n");
            bw.flush();
        }
        else {
            bw.write("No\n");
            bw.flush();
        }
    }
}


分享 spfa复盘

Zycccc
2小时前
import java.io.*;
import java.util.*;

public class Main {
    static final int N = 100010, INF = 0x3f3f3f3f;
    static int n, m, idx;
    static int x, y, z;
    static int[] ne = new int[N], e = new int[N], h = new int[N], w = new int[N], d = new int[N];
    static boolean[] st = new boolean[N];
    static Queue<Integer> q = new LinkedList<>();
    static void add(int a, int b, int c) {
        w[idx] = c;
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static int spfa() {
        Arrays.fill(d, INF);
        d[1] = 0;
        q.offer(1);
        st[1] = true;
        while(!q.isEmpty()) {
            int x = q.poll();
            st[x] = false;
            for (int i = h[x]; i != -1; i = ne[i]) {
                int j = e[i];
                if (d[j] > d[x] + w[i]) {
                    d[j] = d[x] + w[i];
                    if (!st[j]) {
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        return d[n];
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first_line = br.readLine().split(" ");
        n = Integer.parseInt(first_line[0]);
        m = Integer.parseInt(first_line[1]);
        Arrays.fill(h, -1);
        while (m-- != 0) {
            String[] second_line = br.readLine().split(" ");
            x = Integer.parseInt(second_line[0]);
            y = Integer.parseInt(second_line[1]);
            z = Integer.parseInt(second_line[2]);
            add(x, y, z);
        }
        int ans = spfa();
        if (ans > INF / 2) {
            bw.write("impossible\n");
            bw.flush();
        }
        else {
            bw.write(ans + "\n");
            bw.flush();
        }
    }
}



Zycccc
6小时前

循环写法

class Solution {
    private static class Pair {
        int first, second;
        public Pair(int a, int b) {
            this.first = a;
            this.second = b;
        }
    }
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> ans = new ArrayList<>();
        PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->{return a.first - b.first;});
        int n = groupSizes.length;
        for (int i = 0; i < n; i++) q.offer(new Pair(groupSizes[i], i));
        while (true) {
            List<Integer> li = new ArrayList<>();
            while (!q.isEmpty()) {
                Pair p = q.poll();
                int first = p.first;
                int second = p.second;
                li.add(second);
                if (li.size() == first) {
                    ans.add(li);
                    break;
                }
            }
            if (q.isEmpty()) break;
        }
        return ans;
    }
}

深拷贝写法

class Solution {
    private static class Pair {
        int first, second;
        public Pair(int a, int b) {
            this.first = a;
            this.second = b;
        }
    }
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> ans = new ArrayList<>();
        PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->{return a.first - b.first;});
        int n = groupSizes.length;
        for (int i = 0; i < n; i++) q.offer(new Pair(groupSizes[i], i));
        List<Integer> li = new ArrayList<>();
        while (!q.isEmpty()) {
            Pair p = q.poll();
            int first = p.first;
            int second = p.second;
            li.add(second);
            if (li.size() == first) {
                List<Integer> lic = (List<Integer>)((ArrayList<Integer>) li).clone();
                ans.add(lic);
                li.clear();
            }
        }
        return ans;
    }
}


活动打卡代码 LeetCode 1282. 用户分组

Zycccc
6小时前
class Solution {
    private static class Pair {
        int first, second;
        public Pair(int a, int b) {
            this.first = a;
            this.second = b;
        }
    }
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> ans = new ArrayList<>();
        PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->{return a.first - b.first;});
        int n = groupSizes.length;
        for (int i = 0; i < n; i++) q.offer(new Pair(groupSizes[i], i));
        while (true) {
            List<Integer> li = new ArrayList<>();
            while (!q.isEmpty()) {
                Pair p = q.poll();
                int first = p.first;
                int second = p.second;
                li.add(second);
                if (li.size() == first) {
                    ans.add(li);
                    break;
                }
            }
            if (q.isEmpty()) break;
        }
        return ans;
    }
}



Zycccc
1天前
import java.io.*;
import java.util.*;

public class Main {
    static final int N = 200010;
    static int[] e = new int[N], ne = new int[N], h = new int[N], color = new int[N];
    static int n, m, idx;
    static int u, v;
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static boolean dfs(int u, int c) {
        color[u] = c;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (color[j] == 0) {
                if (!dfs(j, 3 - c)) return false;
            }
            else if (color[j] == c) return false;
        }
        return true;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Arrays.fill(h, -1);
        String[] first_line = br.readLine().split(" ");
        n = Integer.parseInt(first_line[0]);
        m = Integer.parseInt(first_line[1]);
        while (m-- != 0) {
            String[] second_line = br.readLine().split(" ");
            u = Integer.parseInt(second_line[0]);
            v = Integer.parseInt(second_line[1]);
            add(u, v);
            add(v, u);
        }
        boolean flag = true;
        for (int i = 1; i <= n; i++) { //必须把每个点都遍历一遍,因为图可能不是一个连通块。
            if (color[i] == 0)
                if (!dfs(i, 1)) {
                    flag = false;
                    break;
                }
        }
        if (!flag) {
            bw.write("No\n");
            bw.flush();
        }
        else {
            bw.write("Yes\n");
            bw.flush();
        }
    }
}



Zycccc
1天前
import java.io.*;
import java.util.*;

public class Main {
    static final int N = 200010;
    static int[] e = new int[N], ne = new int[N], h = new int[N], color = new int[N];
    static int n, m, idx;
    static int u, v;
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static boolean dfs(int u, int c) {
        color[u] = c;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (color[j] == 0) {
                if (!dfs(j, 3 - c)) return false;
            }
            else if (color[j] == c) return false;
        }
        return true;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Arrays.fill(h, -1);
        String[] first_line = br.readLine().split(" ");
        n = Integer.parseInt(first_line[0]);
        m = Integer.parseInt(first_line[1]);
        while (m-- != 0) {
            String[] second_line = br.readLine().split(" ");
            u = Integer.parseInt(second_line[0]);
            v = Integer.parseInt(second_line[1]);
            add(u, v);
            add(v, u);
        }
        boolean flag = true;
        for (int i = 1; i <= n; i++) { //必须把每个点都遍历一遍,因为图可能不是一个连通块。
            if (color[i] == 0)
                if (!dfs(i, 1)) {
                    flag = false;
                    break;
                }
        }
        if (!flag) {
            bw.write("No\n");
            bw.flush();
        }
        else {
            bw.write("Yes\n");
            bw.flush();
        }
    }
}



Zycccc
2天前
import java.io.*;
import java.util.*;

class Edge {
    int a, b, w;
    public Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
}

public class Main {
    static final int N = 200010;
    static int[] p = new int[N];
    static int n, m;
    static int u, v, w;
    static Edge[] edge = new Edge[N];
    static void sort(Edge[] edge, int l, int r) {
        if (l >= r) return;
        int x = edge[l + r >> 1].w, i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (edge[i].w < x);
            do j--; while (edge[j].w > x);
            if (i < j) {
                Edge e = edge[i];
                edge[i] = edge[j];
                edge[j] = e;
            }
        }
        sort(edge, l, j);
        sort(edge, j + 1, r);
    }
    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    static int Kruskal() {
        int res = 0, cnt = 0;
        sort(edge, 0, m - 1);
        for (int i = 0; i < m; i++) {
            int a = edge[i].a;
            int b = edge[i].b;
            int w = edge[i].w;
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                cnt++;
                res += w;
            }
        }
        if (cnt < n - 1) return 0x3f3f3f3f;
        return res;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first_line = br.readLine().split(" ");
        n = Integer.parseInt(first_line[0]);
        m = Integer.parseInt(first_line[1]);
        for (int i = 0; i < m; i++) {
            String[] second_line = br.readLine().split(" ");
            u = Integer.parseInt(second_line[0]);
            v = Integer.parseInt(second_line[1]);
            w = Integer.parseInt(second_line[2]);
            edge[i] = new Edge(u, v, w);
        }
        for (int i = 1; i <= n; i++) p[i] = i;
        int ans = Kruskal();
        if (ans == 0x3f3f3f3f) {
            bw.write("impossible\n");
            bw.flush();
        }
        else {
            bw.write(ans + "\n");
            bw.flush();
        }
    }
}



Zycccc
2天前
import java.io.*;
import java.util.*;

class Edge {
    int a, b, w;
    public Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
}

public class Main {
    static final int N = 200010;
    static int[] p = new int[N];
    static int n, m;
    static int u, v, w;
    static Edge[] edge = new Edge[N];
    static void sort(Edge[] edge, int l, int r) {
        if (l >= r) return;
        int x = edge[l + r >> 1].w, i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (edge[i].w < x);
            do j--; while (edge[j].w > x);
            if (i < j) {
                Edge e = edge[i];
                edge[i] = edge[j];
                edge[j] = e;
            }
        }
        sort(edge, l, j);
        sort(edge, j + 1, r);
    }
    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    static int Kruskal() {
        int res = 0, cnt = 0;
        sort(edge, 0, m - 1);
        for (int i = 0; i < m; i++) {
            int a = edge[i].a;
            int b = edge[i].b;
            int w = edge[i].w;
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                cnt++;
                res += w;
            }
        }
        if (cnt < n - 1) return 0x3f3f3f3f;
        return res;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first_line = br.readLine().split(" ");
        n = Integer.parseInt(first_line[0]);
        m = Integer.parseInt(first_line[1]);
        for (int i = 0; i < m; i++) {
            String[] second_line = br.readLine().split(" ");
            u = Integer.parseInt(second_line[0]);
            v = Integer.parseInt(second_line[1]);
            w = Integer.parseInt(second_line[2]);
            edge[i] = new Edge(u, v, w);
        }
        for (int i = 1; i <= n; i++) p[i] = i;
        int ans = Kruskal();
        if (ans == 0x3f3f3f3f) {
            bw.write("impossible\n");
            bw.flush();
        }
        else {
            bw.write(ans + "\n");
            bw.flush();
        }
    }
}



Zycccc
2天前
import java.io.*;
import java.util.*;

class Edge {
    int a, b, w;
    public Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
}

public class Main {
    static final int N = 200010;
    static int[] p = new int[N];
    static int n, m;
    static int u, v, w;
    static Edge[] edge = new Edge[N];
    static void sort(Edge[] edge, int l, int r) {
        if (l >= r) return;
        int x = edge[l + r >> 1].w, i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (edge[i].w < x);
            do j--; while (edge[j].w > x);
            if (i < j) {
                Edge e = edge[i];
                edge[i] = edge[j];
                edge[j] = e;
            }
        }
        sort(edge, l, j);
        sort(edge, j + 1, r);
    }
    static int find(int x) {
        if (p[x] != x) return find(p[x]);
        return p[x];
    }
    static int Kruskal() {
        int res = 0, cnt = 0;
        sort(edge, 0, m - 1);
        for (int i = 0; i < m; i++) {
            int a = edge[i].a;
            int b = edge[i].b;
            int w = edge[i].w;
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                cnt++;
                res += w;
            }
        }
        if (cnt < n - 1) return 0x3f3f3f3f;
        return res;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first_line = br.readLine().split(" ");
        n = Integer.parseInt(first_line[0]);
        m = Integer.parseInt(first_line[1]);
        for (int i = 0; i < m; i++) {
            String[] second_line = br.readLine().split(" ");
            u = Integer.parseInt(second_line[0]);
            v = Integer.parseInt(second_line[1]);
            w = Integer.parseInt(second_line[2]);
            edge[i] = new Edge(u, v, w);
        }
        for (int i = 1; i <= n; i++) p[i] = i;
        int ans = Kruskal();
        if (ans == 0x3f3f3f3f) {
            bw.write("impossible\n");
            bw.flush();
        }
        else {
            bw.write(ans + "\n");
            bw.flush();
        }
    }
}