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();
}
}
}
分享
Kruskal算法复盘
分享
染色法判定二分图复盘
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复盘
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();
}
}
}
循环写法
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. 用户分组
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;
}
}
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();
}
}
}
活动打卡代码
AcWing 860. 染色法判定二分图
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();
}
}
}
活动打卡代码
AcWing 859. Kruskal算法求最小生成树
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();
}
}
}
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();
}
}
}
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();
}
}
}
