|
|
package 第03期.mca_07;
|
|
|
|
|
|
import java.util.ArrayList;
|
|
|
import java.util.Arrays;
|
|
|
import java.util.List;
|
|
|
import java.util.PriorityQueue;
|
|
|
|
|
|
public class Test {
|
|
|
|
|
|
// n : 1~n, 0~n-1
|
|
|
// edges(无向的！) : [1,5]
|
|
|
// [4,8]
|
|
|
// [3,7]
|
|
|
// 5 9 X
|
|
|
// 有向，带权重 : [1,5,10]
|
|
|
public static ArrayList<ArrayList<Integer>> createGraph(int n, int[][] edges) {
|
|
|
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
|
|
|
// 点的编号，1~n
|
|
|
for (int i = 0; i <= n; i++) {
|
|
|
graph.add(new ArrayList<>());
|
|
|
}
|
|
|
for (int[] e : edges) {
|
|
|
int from = e[0];
|
|
|
int to = e[1];
|
|
|
graph.get(from).add(to);
|
|
|
}
|
|
|
return graph;
|
|
|
}
|
|
|
|
|
|
public static List<Integer> topoSort(int n, ArrayList<ArrayList<Integer>> graph) {
|
|
|
// 点的编号，1~n
|
|
|
int[] inCnts = new int[n + 1];
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
ArrayList<Integer> inexts = graph.get(i);
|
|
|
for (int next : inexts) {
|
|
|
inCnts[next]++;
|
|
|
}
|
|
|
}
|
|
|
int[] queue = new int[n + 1];
|
|
|
int l = 0;
|
|
|
int r = 0;
|
|
|
// 谁入度为0，加入到queue里去！
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
if (inCnts[i] == 0) {
|
|
|
queue[r++] = i;
|
|
|
}
|
|
|
}
|
|
|
List<Integer> ans = new ArrayList<>();
|
|
|
while (l < r) { // 如果队列里还有东西，就继续
|
|
|
// cur就是当前弹出的点
|
|
|
int cur = queue[l++];
|
|
|
// 消除掉cur的影响！
|
|
|
for (int curNext : graph.get(cur)) {
|
|
|
if (--inCnts[curNext] == 0) {
|
|
|
queue[r++] = curNext;
|
|
|
}
|
|
|
}
|
|
|
ans.add(cur);
|
|
|
}
|
|
|
if (ans.size() != n) {
|
|
|
return null;
|
|
|
}
|
|
|
return ans;
|
|
|
}
|
|
|
|
|
|
// edges [3,5,10]
|
|
|
public static int kruskal(int n, int[][] edges) {
|
|
|
// 建图？没必要！
|
|
|
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
|
|
|
UnionFind uf = new UnionFind(n);
|
|
|
// List<int[]> ans =
|
|
|
int ans = 0;
|
|
|
for (int[] edge : edges) {
|
|
|
int a = edge[0];
|
|
|
int b = edge[1];
|
|
|
int weight = edge[2];
|
|
|
if (!uf.isSameSet(a, b)) {
|
|
|
ans += weight;
|
|
|
uf.union(a, b);
|
|
|
}
|
|
|
}
|
|
|
return ans;
|
|
|
}
|
|
|
|
|
|
public static class UnionFind {
|
|
|
|
|
|
public UnionFind(int n) {
|
|
|
// n 0 ~ n-1
|
|
|
// 1 ~ n
|
|
|
|
|
|
}
|
|
|
|
|
|
public boolean isSameSet(int a, int b) {
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
public void union(int a, int b) {
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
// n : 1 ~ n
|
|
|
// start : 源出发点
|
|
|
// graph : 整个图
|
|
|
public static int[] dij(int n, int start, ArrayList<ArrayList<int[]>> graph) {
|
|
|
int[] distance = new int[n + 1];
|
|
|
// distance[0] : start -> 0 0不存在，所以该空间不用！
|
|
|
// distance[1] : start -> 1 最短距离
|
|
|
// distance[i] : start -> i 最短距离
|
|
|
|
|
|
Arrays.fill(distance, -1);
|
|
|
// distance[i] = -1, -1代表，start -> i 记录没求过！
|
|
|
// [点号，cost]
|
|
|
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
|
|
|
// start -> start 0
|
|
|
heap.add(new int[] { start, 0 });
|
|
|
while (!heap.isEmpty()) {
|
|
|
int[] cur = heap.poll();
|
|
|
int i = cur[0];
|
|
|
int cost = cur[1];
|
|
|
if (distance[i] == -1) { // 当前点之前没有弹出过！才处理!
|
|
|
distance[i] = cost;
|
|
|
for (int[] edge : graph.get(i)) {
|
|
|
int next = edge[0];
|
|
|
int weight = edge[1];
|
|
|
if (distance[next] != -1) {
|
|
|
heap.add(new int[] { next, cost + weight });
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return distance;
|
|
|
}
|
|
|
|
|
|
}
|
