个人网站建设小江,西安做义工网站,重庆大山建设有限公司网站,安徽建设信息网官网2024-02-01#xff08;最小生成树#xff0c;二分图#xff09;-CSDN博客 如何证明当前这条边可以被选#xff1f; 假设不选当前边#xff0c;得到了一棵树#xff0c;然后将这条边加上#xff0c;那么必然会出现一个环#xff0c;在这个环上#xff0c;一定可以找出一…2024-02-01最小生成树二分图-CSDN博客 如何证明当前这条边可以被选 假设不选当前边得到了一棵树然后将这条边加上那么必然会出现一个环在这个环上一定可以找出一条不小于当前边的边那么把当前边替换上去结果一定不会变差。 1140. 最短网络 - AcWing题库 Prim算法 裸题 import java.util.*;public class Main{static int N 110;static int n, res;static int[][] g new int[N][N];static int[] dist new int[N];//连通块外的其他点到连通块的最短距离static boolean[] st new boolean[N];//是否在联通块内public static void prim(){Arrays.fill(dist, 0x3f3f3f3f);dist[1] 0;res 0;for(int i 1; i n; i ){int t -1;for(int j 1; j n; j ){if(!st[j] (t -1 || dist[t] dist[j])){t j;}}if(dist[t] 0x3f3f3f3f) return;//不连通直接返回res dist[t];st[t] true;for(int j 1; j n; j ){//更新其他点到连通块的距离dist[j] Math.min(dist[j], g[t][j]);}}System.out.print(res);return;}public static void main(String[] args){Scanner sc new Scanner(System.in);n sc.nextInt();for(int i 1; i n; i ){for(int j 1; j n; j ){g[i][j] sc.nextInt();}}prim();}
} 1141. 局域网 - AcWing题库 相当于在这个图的每个连通块内的一棵最小生成树相当于求原图的“最小生成森林”。 Kruskal算法 1.将所有的边权从小到大排序 2.依次枚举每条边的a b w 如果ab不连通那么就将当前边加入最小生成树中去。 import java.util.*;class PII implements ComparablePII{int a, b, c;public PII(int a, int b, int c){this.a a;this.b b;this.c c;}public int compareTo(PII o){return c - o.c;}
}public class Main{static int N 210;static int n, m, sum;static int[] p new int[N];//并查集static PII[] q new PII[N];public static int find(int x){if(p[x] ! x) p[x] find(p[x]);return p[x];//并查集的基本操作}public static int Kruskal(){Arrays.sort(q, 1, m 1);int res 0;for(int i 1; i m; i ){int a q[i].a;int b q[i].b;int c q[i].c;a find(a);b find(b);if(a ! b){//是否在同一个连通块中p[a] b;res c;//最小生成树的权重之和}}return res;}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 ) p[i] i;for(int i 1; i m; i ){int a sc.nextInt();int b sc.nextInt();int c sc.nextInt();q[i] new PII(a, b, c);sum c;}System.out.print(sum - Kruskal());}
} 1142. 繁忙的都市 - AcWing题库 普通最小生成树权值之和最小 本题最大权值最小 1.将所有边从小到大排序 2.从小到大依次枚举每条边abw 如果ab已经连通直接pass 如果ab不连通那么直接将这条边选出来 import java.util.*;class PII implements ComparablePII{int a, b, c;public PII(int a, int b, int c){this.a a;this.b b;this.c c;}public int compareTo(PII o){return c - o.c;}
}public class Main{static int N 310, M 10010;static int n, m, res, cnt;static int[] p new int[N];static PII[] q new PII[M];public static int find(int x){if(p[x] ! x) p[x] find(p[x]);return p[x];}public static void Kruskal(){Arrays.sort(q, 1, m 1);for(int i 1; i m; i ){int a q[i].a;int b q[i].b;int c q[i].c;a find(a);b find(b);if(a ! b){p[a] b;cnt ;res Math.max(res, c);}}System.out.print(cnt res);}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 ){p[i] i;}for(int i 1; i m; i ){int a sc.nextInt();int b sc.nextInt();int c sc.nextInt();q[i] new PII(a, b, c);}Kruskal();}
} 1143. 联络员 - AcWing题库 //1.先将所有必选边加入并查集 //2.将所有非必选边从小到大排序 //3.依次枚举所有非必选边abw // 如果ab联通直接pass如果不联通就将当前边选上 import java.util.*;class PII implements ComparablePII{int a, b, c;public PII(int a, int b, int c){this.a a;this.b b;this.c c;}public int compareTo(PII o){return c - o.c;}
}public class Main{static int N 2010, M 10010;static int n, m, res, k;static int[] p new int[N];static PII[] q new PII[M];public static int find(int x){if(p[x] ! x) p[x] find(p[x]);return p[x];}public static void Krustral(){Arrays.sort(q, 0, k);for(int i 0; i k; i ){int a q[i].a;int b q[i].b;int c q[i].c;a find(a);b find(b);if(a ! b){p[a] b;res c;}}System.out.print(res);}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 ){p[i] i;}for(int i 1; i m; i ){int t sc.nextInt();int a sc.nextInt();int b sc.nextInt();int c sc.nextInt();if(t 1){p[find(a)] find(b);res c;}else{q[k ] new PII(a, b, c);}}Krustral();}
} 1144. 连接格点 - AcWing题库
import java.util.*;class PII implements ComparablePII{int a, b, c;public PII(int a, int b, int c){this.a a;this.b b;this.c c;}public int compareTo(PII o){return c - o.c;}
}public class Main{static int N 1010, M N * N, K 2 * M;static int n, m, k, res;static PII[] q new PII[K];static int[] p new int[M];static int[][] g new int[N][N];public static int find(int x){if(x ! p[x]) p[x] find(p[x]);return p[x];}public static void get_PII(){int[] dx {-1, 0, 1, 0}, dy {0, 1, 0, -1}, dw {1, 2, 1, 2};for(int z 0; z 2; z ){for(int i 1; i n; i ){for(int j 1; j m; j ){for(int u 0; u 4; u ){if(u % 2 z){int x i dx[u], y j dy[u];if(x 0 || y 0 || x n || y m) continue;int a g[i][j], b g[x][y], w dw[u];if(a b) q[k ] new PII(a, b, w);}}}}}}public static void main(String[] args){Scanner sc new Scanner(System.in);n sc.nextInt();m sc.nextInt();for(int i 1; i n * m; i ){p[i] i;}int cnt 0;for(int i 1; i n; i ){//给每个点编号for(int j 1; j m; j ){g[i][j] cnt;}}get_PII();while(sc.hasNext()){int x1 sc.nextInt();int y1 sc.nextInt();int x2 sc.nextInt();int y2 sc.nextInt();int a g[x1][y1], b g[x2][y2];p[find(a)] find(b);}for(int i 0; i k; i ){int a q[i].a;int b q[i].b;int c q[i].c;a find(a);b find(b);if(a ! b){p[a] b;res c;}}System.out.print(res);}
}
