第十三周.

我会带着你远行 2022-10-16 14:26 194阅读 0赞

### 记录 ###

*  A、迷路的牛牛
 *   *   *  代码
 *  B、工作单位
 *   *   *  代码
 *  C、隔离14天
 *   *   *  代码
 *  D、最小生成树（Kruskal）
 *   *   *  代码
 *  E、搭建电路
 *   *   *  代码
 *  F、单源最短路径问题
 *   *   *  代码

# A、迷路的牛牛 #

**题目描述**

*  牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。

**输入**

*  每个输入包含一个测试用例。 每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。  
    接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。

**输出**

*  输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。

**样例输入 Copy**

3
    LRR

**样例输出 Copy**

### 代码 ###

链接：[迷路的牛牛][Link 1]

import java.util.Scanner;
    
    public class Main { 
    	
    	public static void direction(int count_L,int count_R){ 
    		//左转的次数可以和右转的次数抵消，剩下的都是左转或者右转
    		int real = Math.abs(count_L-count_R);//剩下的
    		int temp = count_L > count_R ? 2:0;
    		
    		if(real%4==0)
    			System.out.println("N");
    		else if(real%4==1+temp)
    			System.out.println("E");
    		else if(real%4==2)
    			System.out.println("S");
    		else if(real%4==3-temp)
    			System.out.println("W");
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();
    			String str = sc.next();
    			int count_L = 0;
    			int count_R = 0;
    			for(int i=0;i<str.length();i++){ 
    				if(str.charAt(i)==('L'))
    					count_L++;//左转的次数
    				else
    					count_R++;//右转的次数
    			}
    			direction(count_L,count_R);
    		}
    	}
    
    }

# B、工作单位 #

**题目描述**

*  在某个城市中住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。
 *  假设所有认识的人一定属于同一个单位，请计算该城市有多少个单位？

**输入**

*  第1行的第1个值表示总人数n，第2个值表示总信息数m；第2行开始为具体的认识关系信息

**输出**

*  单位的个数

**样例输入 Copy**

10 4
    2 3
    4 5
    4 8
    5 8

**样例输出 Copy**

链接：[工作单位][Link 2]（嗯，就是并查集的代码）

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    	private static int[] parent = new int[200];
    	private static int[] rank = new int[200];
    	public static int count;
    
    	public static void init(int x){ //初始化每个集合（树）,将每个元素作为一个集合
    		parent[x] = x;
    		rank[x] = 1;
    	}
    	public static int find_set(int x){ //路径压缩，递归的将每个节点的根节点指向整棵树的根节点
    		if(parent[x]!=x)
    			return find_set(parent[x]);
    		return parent[x];
    	}
    	public static void union_set(int x,int y){ 
    		int a = find_set(x);
    		int b = find_set(y);
    		if(a==b)   //如果相等就代表在同一棵树，在同一个集合
    			return;
    		count--;//集合的个数少1
    		
    		if(rank[a]<=rank[b]){ //如果a的秩小于等于b的秩，则将a合并到b
    			parent[a] = b;
    			if(rank[a]==rank[b])//如果a,b的秩相等，则需要将b的秩加一
    				rank[b]++;
    		}
    		else
    			parent[b] = a;//如果b的秩小于a的秩，则将b合并到a
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();//住着n个人
    			int m = sc.nextInt();//m条信息
    			for(int i=1;i<=n;i++)
    				init(i);
    			count = n;
    			for(int i=0;i<m;i++){ 
    				int x = sc.nextInt();
    				int y = sc.nextInt();
    				union_set(x,y);
    			}
    			System.out.println(count);
    		}
    
    	}
    
    }

# C、隔离14天 #

**题目描述**

*  如果实施更为严格的防控措施，一辆汽车上有一个确诊患者或者密切接触者，那么该汽车上所有的人都被认为是密切接触者，全部需要自行居家隔离或者集中隔离14天。
 *  现在假定编号为0的乘客冠状病毒核酸检验呈阳性，请编写一个程序统计需隔离的总人数（包括编号为0的乘客）。

**输入**

*  第1行的第1个数字n表示总人数，第2个数字m表示汽车数量；从第2行开始，接下来的m行表示每辆汽车的司乘人员总人数和人员编号（人员编号是一个固定值，可以对应于我们的身份证号码），每一行的第1个数字k表示该汽车的司乘人员总数，接下来的k个数字表示每一个人的编号。

**输出**

*  需要被隔离的总人数。

**样例输入 Copy**

100 4
    2 1 2
    5 10 13 11 12 14
    2 0 1
    2 99 2

**样例输出 Copy**

链接：[隔离14天][Link 2]

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    	static int parent[] = new int[10000];//存放父节点
    	static int rank[] = new int[10000];//存放秩
    	static int count;
    	
    	public static void init(int x){ //初始化每个集合（树）,将每个元素作为一个集合
    		parent[x] = x;
    		rank[x] = 0;
    	}
    	public static int find_set(int x){ //路径压缩，递归的将每个节点的根节点指向整棵树的根节点
    		if(parent[x]!=x)
    			parent[x] = find_set(parent[x]);
    		return parent[x];
    	}
    	public static void union_set(int x,int y){ 
    		int a = find_set(x);
    		int b = find_set(y);
    		if(a==b)   //如果相等就代表在同一棵树，在同一个集合
    			return;
    		if(rank[a]<=rank[b]){ //如果a的秩小于等于b的秩，则将a合并到b
    			parent[a] = b;
    			if(rank[a]==rank[b])//如果a,b的秩相等，则需要将b的秩加一
    				rank[b]++;
    		}
    		else
    			parent[b] = a;//如果b的秩小于a的秩，则将b合并到a
    	}
    
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();//总人数
    			int m = sc.nextInt();//汽车数量
    			
    				for(int i=0;i<=n;i++)
    					init(i);//初始化，i<=0，避免为0时不能初始化
    				
    				for(int i=0;i<m;i++){ 
    					int k = sc.nextInt();
    					int x = sc.nextInt();
    					for(int j=1;j<k;j++){ 
    						int y = sc.nextInt();
    						union_set(x,y);
    					}
    				}
    				count = 0;
    				for(int j=0;j<n;j++)
    					if(find_set(j)==find_set(0))
    						count++;
    				System.out.println(count);
    			
    		}
    
    	}
    
    }

# D、最小生成树（Kruskal） #

**题目描述**

*  编程实现Kruskal算法，求图的最小生成树(MST)的权重。

**输入**

*  每组数据分为两个部分，第一部分为图的点数n，和边数m, 第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

**输出**

*  最小生成树的权重。

**样例输入 Copy**

3 3
    0 1 10
    0 2 15
    1 2 50

**样例输出 Copy**

链接：[最小生成树][Link 2]

### 代码 ###

#include<bits/stdc++.h>
    
    #define ll long long
    const int N=1005;
    using namespace std;
    
    int p[N];//用来存放每个点的父节点
    int ran[N];//用来存放秩，用来优化，减少树的高度
    double sm;//用来存放结果，权重
    typedef struct{ //定义每条边
        int x,y;
        double v;
    }Node;
    Node node[N];
    bool cmp(Node& a,Node& b){ //升序
        return a.v<b.v;
    }
    void init(int x){ //初始化每个节点，使每个节点的父节点为它自己
        p[x]=x;
        ran[x]=0;
    }
    int findp(int x){ //用来寻找父节点，用来判断是否在同一个树，同时使用路径压缩优化
        if(p[x]!=x)
            p[x]=findp(p[x]);
        return p[x];
    }
    bool merg(int x,int y,double v){ //用来合并2棵树，按照秩来合并，小的合并到大的上面去，并进行权值操作
        int a=findp(x);
        int b=findp(y);
        if(a==b)
            return false ;
        if(ran[a]>ran[b]){ 
                p[b]=a;
                sm+=v;
            }else{ 
                p[a]=b;
                sm+=v;
                if(ran[a]==ran[b])
                    ran[b]++;
            }
            return true;
    
    }
    
    int main()
    { 
    
    	int n, m;
    
        while(cin>>n>>m){ 
               sm=0;
                    for(int i=0;i<n;i++){ 
                        init(i);
                    }
            for(int i=0;i<m;i++){ 
                cin>>node[i].x>>node[i].y>>node[i].v;
            }
            sort(node,node+m,cmp);//排序
            for(int j=0;j<m;j++){ 
                merg(node[j].x,node[j].y,node[j].v);//并查集判断，是否在同一棵树上（也就是这2点是否已经存在这棵树里面）
            }
        printf("%.0lf\n",sm);
        }
    
    
    }

# E、搭建电路 #

**Description**

*  明明迷上了一个搭建电路的游戏。 在游戏中，每次在两个电子元件之间增加一条有效电路（两个元件之间先前没有电路相连）都将获得相应的积分奖励。  
    已知电子元件数量n和部分电子元件之间的奖励积分值。如何构建一个有效电路将所有元件全部连接起来，并且可以得到最多的积分奖励。

**Input**

*  每组输入数据包含m+1行。 第1行输入两个正整数n和m，其中n表示电子元件数量（n<=100），m表示提供了m对电子元件之间的奖励积分值（m<=1000）。两个正整数之间用空格隔开。
 *  第2行到第m+1行对应m对电子元件及其对应的奖励积分值，每一行包含三个正整数，第1个和第2个整数表示电子元件编号（从1开始），第3个整数表示两个元件之间搭建电路的奖励积分num(num<1e9)。整数之间用空格隔开。

**Output**

*  每组输出占1行，输出一个正整数，即最多可以得到的积分奖励值。如果没有办法把所有元件全部连接起来，则输出“No solution.”。

**Sample Input Copy**

3 3
    1 2 10
    1 3 20
    2 3 30

**Sample Output Copy**

### 代码 ###

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
     
    const int MAXN=1010;
    int fa[MAXN];
    int ra[MAXN];
    ll ans;
     
    struct Edge{ 
        int x;
        int y;
        int cost;
    };
     
    int cmp(const Edge &x,const Edge &y){ 
        return x.cost>y.cost;
    }
     
    int find_set(int x){ 
        if(x!=fa[x]){ 
            fa[x]=find_set(fa[x]);
        }
        return fa[x];
    }
     
    void union_set(int x,int y,int cost){ 
        x=find_set(x);
        y=find_set(y);
        if(x!=y) ans+=cost;
        if(ra[x]>ra[y]) fa[y]=x;
        else{ 
            fa[x]=y;
            if(ra[x]==ra[y]){ 
                ra[y]++;
            }
        }
    }
     
    int main(){ 
        int n,m;
        while(cin>>n>>m){ 
            Edge es[MAXN];
            memset(fa,0,sizeof(fa));
            memset(ra,0,sizeof(ra));
            for(int i=1;i<n;i++){ 
                fa[i]=i;
                ra[i]=0;
            }
            for(int i=0;i<m;i++){ 
                cin>>es[i].x>>es[i].y>>es[i].cost;
            }
            sort(es,es+m,cmp);
            ans=0;
            if(m>=n-1){ 
                for(int i=0;i<m;i++){ 
                    union_set(es[i].x,es[i].y,es[i].cost);
                }
                int f=0;
                for(int i=0;i<n-1;i++){ 
                    if(fa[i]!=fa[i+1]){ 
                        f=1;
                    }
                }
                if(f==0) cout<<ans<<endl;
                else cout<<"No solution."<<endl;
            }
            else cout<<"No solution."<<endl;
            
        }
        return 0;
    }

# F、单源最短路径问题 #

**题目描述**

*  编程实现Dijkstra算法，求一个有向加权图中，从源点出发到其他各个顶点的最短路径。

**输入**

*  第1行第1个值表示顶点个数，第2个值表示边个数；第2行开始为边（两个顶点，边的起点和终点）及权重。

**输出**

*  顶点0到每一个顶点的最短路径长度。

**样例输入 Copy**

5 7
    0 1 10
    0 3 30
    0 4 100
    1 2 50
    2 4 10
    3 2 20
    3 4 60

**样例输出 Copy**

0 10 50 30 60

链接 ：[单源最短路径][Link 2]

### 代码 ###

import java.util.Scanner;
    
    public class Main { 
    	public static void dijkstra(int[][] G,int[] dist){ 
    		int n = dist.length;
    		boolean[] s = new boolean[n];//标记顶点放入或不放入
    		//初始化点0到各个定点的初始距离
    		for(int i=1;i<n;i++)
    			dist[i] = G[0][i];
    		dist[0] = 0;//第一个点到自己为0
    		s[0] = true;//初始默认选择点1
    		int current = 0;
    		for(int i = 0;i < n;i++){ //共扫描n-1次
    			int min = 1000000;
    			//寻找距离点0最近的点
    			
    			for(int j=0;j<n;j++)//循环找到下一个距离最短的点
    				if(!s[j]&&dist[j]<min){ 
    					current = j;
    					min = dist[j];
    				}
    			//设置这个距离点0的点被选中
    				s[current] = true;
    				for(int k=1;k<n;k++)//循环更改每个点的最短距离
    					if((!s[k])&&(dist[current]+G[current][k])<dist[k])
    							dist[k] = dist[current]+G[current][k];
    		}
    		for(int i=0;i<n;i++){ 
    			System.out.print(dist[i]+" ");
    		}
    	}
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()){ 
    			int n = sc.nextInt();//点数
    			int m = sc.nextInt();//边数
    			int[][] G = new int[n][n];//下标从1开始，以下都是
    			int[] dist = new int[n]; 
    			for(int i=0;i<n;i++)//初始化边
    				for(int j=0;j<n;j++){ 
    					if(i==j)
    						G[i][j] = 0;
    					else
    						G[i][j] = 1000000;
    				}
    			
    			for(int i=0;i<m;i++){ 
    				int x = sc.nextInt();
    				int y = sc.nextInt();
    				int weight = sc.nextInt();
    				G[x][y] = G[y][x] = weight;
    			}
    			dijkstra(G,dist);
    			System.out.println("\n");
    		}
    	}
    }

> 【今天和室友们浅谈了一下未来的规划，感觉未来挺迷茫的，但是周一还是要继续干学习呀！】
> 
> > “我的图能不能尽量不修，如果非修的话，能不能别把我的皱纹都给我修平了，那可是我好不容易长出来的，年龄不是我的敌人，我的故事写在我的脸上，而这张脸就是对时间，对真实的致敬”

[Link 1]: https://blog.csdn.net/u010707315/article/details/98180775
[Link 2]: https://blog.csdn.net/qq_43520913/article/details/105937098