hnucm_oj 算法分析与设计 练习13
问题 A: 迷路的牛牛
题目描述
牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。
输入
每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。
输出
输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。
样例输入
3
LRR
样例输出
E
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
sc.nextLine();
String a = sc.nextLine();
char[] b = a.toCharArray();
int L=0,R=0,c=0;
for(int i=0;i<n;i++) {
if(b[i]=='R') {
R++;
}
else {
L++;
}
}
if(R>L) {
c=(R-L)%4;
if(c==0) {
System.out.println("N");
}
else if(c==1) {
System.out.println("E");
}
else if(c==2) {
System.out.println("S");
}
else if(c==3) {
System.out.println("W");
}
}
else {
c=(L-R)%4;
if(c==0) {
System.out.println("N");
}
else if(c==1) {
System.out.println("W");
}
else if(c==2) {
System.out.println("S");
}
else if(c==3) {
System.out.println("E");
}
}
}
}
}
问题 B: 工作单位
题目描述
在某个城市中住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。
假设所有认识的人一定属于同一个单位，请计算该城市有多少个单位？
输入
第1行的第1个值表示总人数n，第2个值表示总信息数m；第2行开始为具体的认识关系信息
输出
单位的个数
样例输入
10 4
2 3
4 5
4 8
5 8
样例输出
7
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n+1];
int count=1;
for(int i=0;i<m;i++) {
int j = sc.nextInt();
int k = sc.nextInt();
if(a[j]==0&&a[k]==0) {
a[j]=count;
a[k]=count;
count++;
}
else if(a[j]!=0&&a[k]==0) {
a[k]=a[j];
}
else if(a[k]!=0&&a[j]==0) {
a[j]=a[k];
}
else if(a[j]!=a[k]&&a[j]!=0&&a[k]!=0) {
if(a[j]<a[k]) {
for(int p=1;p<=n;p++) {
if(a[p]==a[k]) {
a[p]=a[j];
}
}
}
else {
for(int p=1;p<=n;p++) {
if(a[p]==a[j]) {
a[p]=a[k];
}
}
}
}
}
int rel=0,flag=0;
for(int i=1;i<=n;i++) {
if(a[i]==0) {
rel++;
}
}
for(int i=1;i<count;i++) {
flag=0;
for(int j=1;j<=n;j++) {
if(a[j]==i) {
flag=1;
break;
}
}
if(flag==1) {
rel++;
}
}
System.out.println(rel);
}
}
}
PS：并查集用一个数组代替，不同的数字代表不同的集合。
问题 C: 隔离14天
题目描述
……
如果实施更为严格的防控措施，一辆汽车上有一个确诊患者或者密切接触者，那么该汽车上所有的人都被认为是密切接触者，全部需要自行居家隔离或者集中隔离14天。
现在假定编号为0的乘客冠状病毒核酸检验呈阳性，请编写一个程序统计需隔离的总人数（包括编号为0的乘客）。
输入
第1行的第1个数字n表示总人数，第2个数字m表示汽车数量；从第2行开始，接下来的m行表示每辆汽车的司乘人员总人数和人员编号（人员编号是一个固定值，可以对应于我们的身份证号码），每一行的第1个数字k表示该汽车的司乘人员总数，接下来的k个数字表示每一个人的编号。
输出
需要被隔离的总人数。
样例输入
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
样例输出
4
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
int[] b = new int[m];
int count=1;
for(int i=0;i<m;i++) {
b[i]=sc.nextInt();
int[] c = new int[b[i]];
for(int j=0;j<b[i];j++) {
c[j]=sc.nextInt();
}
for(int j=0;j<b[i];j++) {
if(a[c[j]]==0) {
a[c[j]]=count;
}
else {
for(int k=0;k<b[i];k++) {
a[c[k]]=a[c[j]];
}
}
}
count++;
}
count=0;
for(int i=0;i<n;i++) {
if(a[i]==a[0]) {
count++;
}
}
System.out.println(count);
}
}
}
PS：同一辆车上的人属于一个集合，如果两辆车上有相同的人，两辆车上的人属于一个集合。
问题 D: 最小生成树（Kruskal）
题目描述
编程实现Kruskal算法，求图的最小生成树(MST)的权重。
输入
每组数据分为两个部分，第一部分为图的点数n，和边数m,
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。
输出
最小生成树的权重。
样例输入
3 3
0 1 10
0 2 15
1 2 50
样例输出
25
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[m];
int[] b = new int[m];
int[] c = new int[m];
int[] d = new int[n];
int count=1,sum=0;
for(int i=0;i<m;i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
c[i] = sc.nextInt();
}
for(int i=0;i<m-1;i++) {
for(int j=0;j<m-1;j++) {
if(c[j]>c[j+1]) {
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
t = b[j];
b[j] = b[j+1];
b[j+1] = t;
t = c[j];
c[j] = c[j+1];
c[j+1] = t;
}
}
}
for(int i=0;i<n-1;i++) {
if(d[a[i]]==0&&d[b[i]]==0) {
d[a[i]]=count;
d[b[i]]=count;
count++;
sum+=c[i];
}
else if(d[a[i]]!=0&&d[b[i]]==0) {
d[b[i]]=d[a[i]];
sum+=c[i];
}
else if(d[a[i]]==0&&d[b[i]]!=0) {
d[a[i]]=d[b[i]];
sum+=c[i];
}
else if(d[a[i]]!=0&&d[b[i]]!=0&&d[a[i]]!=d[b[i]]) {
for(int j=0;j<n;j++) {
if(d[j]==d[b[i]]) {
d[j]=d[a[i]];
}
}
sum+=c[i];
}
}
System.out.println(sum);
}
}
}
问题 E: 搭建电路
题目描述
明明迷上了一个搭建电路的游戏。
在游戏中，每次在两个电子元件之间增加一条有效电路（两个元件之间先前没有电路相连）都将获得相应的积分奖励。
已知电子元件数量n和部分电子元件之间的奖励积分值。如何构建一个有效电路将所有元件全部连接起来，并且可以得到最多的积分奖励。
输入
每组输入数据包含m+1行。
第1行输入两个正整数n和m，其中n表示电子元件数量（n<=100），m表示提供了m对电子元件之间的奖励积分值（m<=1000）。两个正整数之间用空格隔开。
第2行到第m+1行对应m对电子元件及其对应的奖励积分值，每一行包含三个正整数，第1个和第2个整数表示电子元件编号（从1开始），第3个整数表示两个元件之间搭建电路的奖励积分num(num<1e9)。整数之间用空格隔开。
输出
每组输出占1行，输出一个正整数，即最多可以得到的积分奖励值。如果没有办法把所有元件全部连接起来，则输出“No solution.”。
样例输入
3 3
1 2 10
1 3 20
2 3 30
样例输出
50
代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[m];
int[] b = new int[m];
int[] c = new int[m];
int[] d = new int[n];//并查集
int count=1,t;
long sum = 0;
for(int i=0;i<m;i++) {
a[i] = sc.nextInt()-1;
b[i] = sc.nextInt()-1;
c[i] = sc.nextInt();
}
if(m<n-1) {
System.out.println("No solution.");
}
else {
for(int i=0;i<m-1;i++) {
for(int j=0;j<m-1;j++) {
if(c[j]<c[j+1]) {
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
t = b[j];
b[j] = b[j+1];
b[j+1] = t;
t = c[j];
c[j] = c[j+1];
c[j+1] = t;
}
}
}
/*for(int i=0;i<m;i++) {
System.out.println(a[i]+" "+b[i]+" "+c[i]);
}*/
for(int i=0;i<m;i++) {
if(d[a[i]]==0&&d[b[i]]==0) {
d[a[i]] = count;
d[b[i]] = count;
count++;
sum+= c[i];
}
else if(d[a[i]]!=0&&d[b[i]]==0) {
d[b[i]] = d[a[i]];
sum+= c[i];
}
else if(d[a[i]]==0&&d[b[i]]!=0) {
d[a[i]] = d[b[i]];
sum+= c[i];
}
else if(d[a[i]]!=0&&d[b[i]]!=0&&d[a[i]]!=d[b[i]]) {
int flag = d[b[i]];
for(int j=0;j<n;j++) {
if(d[j]==flag) {
d[j] = d[a[i]];
}
}
sum+= c[i];
}
}
int flag=0;
for(int i=0;i<n-1;i++) {
if(d[i]!=d[i+1]) {
flag = 1;
}
}
if(flag==0) {
System.out.println(sum);
}
else {
System.out.println("No solution.");
}
}
}
}
}
PS：主要记录结果的变量要用long(