北邮2014年网研机试

## Problem A. 分数加法

### 题目描述

[题目链接](https://vpn.bupt.edu.cn/http/10.105.242.80/problem/p/266/)

求2-a + 2-b，其中a和b均为正整数，结果请用最简分数表示。

### 输入格式
第一行为测试数据的组数T（1<=T<=400）。请注意，任意两组测试数据之间是相互独立的。
每组测试数据一行，包含两个整数a和b（2<=a,b<=20）。

### 输出格式

对于每组测试数据，在一行内输出结果，分子和分母用“/”隔开。

### 输入样例

```
2
2 4
3 2
```

### 输出样例

```
5/16
3/8
```

### 思路解析
* 可能没考虑到是化简成最简分数。我一开始认为不可能需要化简呀！下面是偶数，上面是偶数+1一定是奇数，怎么还要化简呢...后来才发现，上面也可能是1+1，即a=b的情况

### AC代码

```
package bupt;

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num = scanner.nextInt();
		
		for (int i = 0; i < num; i++) {
			int a = scanner.nextInt();
			int b =scanner.nextInt();
			
			int max= Math.max(a, b);
			int min = Math.min(a, b);
			
			int down = (int) Math.pow(2, max);
			int up = (int) Math.pow(2, max-min);
			up = up + 1;
			
			while (up%2==0){
	            up/=2;
	            down/=2;
	        }// 比如 1/4 + 1/4 就需要化简成最简分数
			System.out.println(up + "/" + down);
		}
	}
}
```

## Problem B. 最小堆

### 题目描述

[题目链接](https://vpn.bupt.edu.cn/http/10.105.242.80/problem/p/267/)

给定一棵带权二叉树，请判断它是不是一个最小堆。
一棵二叉树是一个最小堆，当且仅当对于树上任意一个节点，它的权值都小于或等于以它为根的子树中的所有权值。

### 输入格式
输入数据第一行是一个整数T（1<=T<=100），表示测试数据的组数。
对于每组测试数据：
第一行是一个整数N（1<=N<=100），表示树的节点个数。
接下来一行包含N个正整数，第i个整数valuei(1<=valuei<=1000)表示编号i的点的权值。
接下来N-1行，每行两个整数u和v（1<=u，v<=N, u!=v），表示节点u是节点v的父节点。
测试数据保证给定的一定是一棵二叉树，并且节点1是树的根结点。

### 输出格式
对于每组测试数据，如果给定的树是一个最小堆则输出Yes，否则输出No。

### 输入样例

```
3
1
10
3
10 5 3
1 2
1 3
5
1 2 3 4 5
1 3
1 2
2 4
2 5
```

### 输出样例

```
Yes
No
Yes
```

### 思路解析

* 这题因为只是判断是不是最小堆，都不需要表示树，只要存储每个顶点的权值即可。然后边输入边变判断起点权值是否小于终点权值即可。
* 一般OJ题对普通树表示方法有**父亲表示法**（命名树一个节点只有一个父亲，偏偏叫双亲表示法，我服了），**孩子表示法**，**孩子兄弟表示法**。
* 对二叉树表示方法。

> 父亲表示法

就是一个一维数组，数组的元素序号表示顶点编号，值表示该顶点的父亲节点编号。

### AC代码

```java
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num = scanner.nextInt();
		for (int i = 0; i < num; i++) {
			int N = scanner.nextInt();//the number of vertexes;
			int[] vetexs = new int[101];
			
			for (int j = 1; j <= N; j++) {
				//input weight of vertexes
				vetexs[j] = scanner.nextInt();
			}
			
			boolean flag = true;
			for (int j = 0; j < N-1; j++) {
				//input relationship of edges
				int parent = scanner.nextInt();
				int child = scanner.nextInt();
				
				if (vetexs[parent] > vetexs[child]) {
					if (flag) {
						flag = false;
					}
				}
			}
			if (flag) {
				System.out.println("Yes");
			}else {
				System.out.println("No");
			}
		}	
		scanner.close();
	}
}
```

## Problem C. 进程管理

### 题目描述

[题目链接](https://vpn.bupt.edu.cn/http/10.105.242.80/problem/p/268/)

在操作系统中，进程管理是非常重要的工作，每个进程都有唯一的进程标识（PID）。每个进程都可以启动子进程，此时我们称它为其子进程的父进程，除了PID为0的进程之外，每个进程有且只有一个父进程，在这个任务中，你需要实时维护操作系统运行中的三个基本操作：

FORK PID1 PID2：标识为PID1的进程启动了一个标识为PID2的子进程。
KILL PID：结束标识为PID的进程。请注意，与此同时所有PID的子进程也将同时结束。如果PID是不存在或已经结束的进程，则不做任何操作。
QUERY PID：查询标识为PID的进程是否仍然存在。
在初始状态下，系统只开启了PID为0的进程，并且在任何情况下该进
程不会结束。

### 输入格式
输入的第一行是一个整数T（T<=50），表示输入的数据组数。
每组测试数据的第一行是一个整数N（1<=N<=100），表示操作的数量。
每下来N行，每行按照上面的描述给出每个操作，输入保证所有的进程的PID都不相同，且一个进程结束后不会被重新启动，所有PID都是[1,100]之间的整数。

### 输出格式
对于每次QUERY查询，如果进程存在，输出Yes，不存在则输出No

### 输入样例

```java
2
5
FORK 0 1
QUERY 1
KILL 1
QUERY 1
QUERY 2
1
QUERY 0
```

### 输出样例

```
Yes
No
No
Yes
```

> 参考链接：[BOJ 解题报告-268进程管理](https://antarx.com/2017/03/11/268/#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E5%A4%84%E7%90%86)

### 思路解析

* KILL 是本题的难点和坑的地方。KILL PID，子进程的子进程也需要KILL掉。所以**一种方法**每个进程有一个子进程列表的成员变量。在FORK的时候，就链式将当前进程沿着父进程的方向，加到沿途的每一个父进程的子进程列表中。（我是这么做的）另一个方法是KILL时候递归删除（没能理解！）

* 比如`FORK 0 1`的输入，因为**java不能格式化输入，只能格式化输出**。见下面具体说明。

* list remove方法。remove(int index)与remove(Object o)这两个函数完全不同。第一个remove很好理解，按照索引删除。第二个是是将`Object o` 与`List<Object>list`使用equals函数进行循环匹配，所以必须重写equals函数。Object.equals(Object o)这个函数也有很多注意点。我暂且列举两篇文章：

* [ArrayList的remove()方法](https://www.jianshu.com/p/c1fb6a26a136)
    * [浅谈Java中的equals和==](https://www.cnblogs.com/dolphin0520/p/3592500.html)

（循环遍历删除某个元素，还可以用listIterater.remove()删除当前元素）

> `next()`与`nextLine()`输入区别

**`nextInt()`之类函数与`next()`特性一致。**

* `next()` 必须先进行有效输入（回车、换行、TAB、空格都是无效输入）才能结束输入（否则一直是等待输入的状态），然后再使用结束符号结束当前输入（回车、换行、TAB、空格的任一种）
* `nextLine()`：就没有上面约束了，但是结束符号只有回车一个，所以可以输入含有空格的字符串。但是这个函数会接收回车符。

这两个函数的结束符号虽然都有一个`回车\n`，但是并不一样：
* next() 回车后，`\n` 不会消失（要么被下一个next()过滤，要么被`nextLine()接收`），
* nextLine() 回车后则会直接消失掉，所以下一个`nextLine()`可以正常接收输入，而不会接收到`回车`。

比如我先输入的`5`，其实输入的是`5\n`这个`\n`作为`nextInt()`结束符，但是`\n` 并不会消失，如果下面是`nextLine()` 就会被接收到。

所以本题在循环输入操作条件之前，先用下面一行接收掉没有消失的回车，再用`nextLine()`接收带有空格的操作字符串。最后用split(" ")分离字符串即可。

```java
scanner.nextLine();//Receive enter symbol
```

### AC代码

```java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;

public class Process {
	public static Scanner scanner;
	
	public List<Aprocess> list = new ArrayList<Aprocess>();

public static void main(String[] args) {
		scanner = new Scanner(System.in);
		int num  = scanner.nextInt();
		for (int i = 0; i < num; i++) {
			Process process = new Process();
			process.handle();		
		}
	}
	
	public void handle(){
		int N = scanner.nextInt();
		list.add(new Aprocess("0","0"));
		scanner.nextLine();//Receive enter symbol
		for (int j = 0; j < N; j++) {
			String operation = scanner.nextLine();
			String[] array = operation.split(" ");
			if (array[0].equals("QUERY")) {
				int index = queryPidInList(array[1]);
				if (index != -1) {
					System.out.println("Yes");
				}else{
					System.out.println("No");
				}
			}else if (array[0].equals("FORK")) {
				forkPidInList(array[2],array[1]);
			}else if (array[0].equals("KILL")) {
				killPidInList(array[1]);
			}
		}
	}
	
	public int queryPidInList(String pid){
	
		for (ListIterator<Aprocess> iterator = list.listIterator(); iterator.hasNext();) {
			Aprocess aprocess = (Aprocess) iterator.next();
			if (pid.equals(aprocess.PID)) {
				return iterator.nextIndex() -1;
			}
		}
		return -1;
	}
	
	public void forkPidInList(String pid,String parent){
		int parentIndex = queryPidInList(parent);
		if (parentIndex != -1) {
			Aprocess newAprocess = new Aprocess(pid, parent);
			list.add(newAprocess);
			while(true){
				if (list.get(parentIndex).PID.equals("0")) {
					break;
				}
				list.get(parentIndex).childPid.add(newAprocess);
				parentIndex = queryPidInList(list.get(parentIndex).parentPid);
			}
		}
		
	}
	
	
	public void killPidInList(String pid){
		if (!pid.equals("0")) {
			int pidIndex = queryPidInList(pid);
			if (pidIndex!=-1) {
				List<Aprocess> lStrings = list.get(pidIndex).childPid;
				for (Iterator<Aprocess> iterator = lStrings.iterator(); iterator.hasNext();) {
					Aprocess aprocess = (Aprocess) iterator.next();
					list.remove(aprocess);
				}
				list.remove(pidIndex);
			}		
		}
	}

class Aprocess{
		String PID;
		String parentPid;
		List<Aprocess> childPid = new ArrayList<Aprocess>();
		
		public Aprocess() {
		}
		public Aprocess(String pid){
			this.PID = pid;
			this.parentPid = "0";
		}
		
		public Aprocess(String pid,String parent){
			this.PID = pid;
			this.parentPid = parent;
		}
		
		
		@Override
		public boolean equals(Object obj) {
			if (this.PID.equals(((Aprocess)obj).PID)) {
				return true;
			}
			return false;
		}
	}
}

```

## Problem D. 网络传输

### 题目描述

[题目链接](https://vpn.bupt.edu.cn/http/10.105.242.80/problem/p/269/)

网络的高效互联与智能传输是提升海量用户服务请求映射效率的重要措施。在这个任务中，你要用最少的传输时间，将特定的数据源发送到指定的网络节点中。
我们给定的网络一共包含N个节点（从1到N编号），其中节点1为数据源。网络中有M条无向边（u,v,w），表示一条传输线连接节点u和节点v，且数据通过这条传输线的平均时间为w。由于传送机制的限制，当一个节点接收到数据之后，它只能选择与它互连的一个节点，并将数据转发到该节点。节点1在初始化时只会发送一次数据，但在传输过程中它可以作为转发节点。
网络中有k个目标节点，你需要计算出该数据从节点1传送到所有K个节点所需要的最短时间。注意目标节点可以按任意顺序进行传送，数据也可以多次经过同一节点。

### 输入格式

输入数据第一行是一个整数T（T<=5），表示测试数据的组数。
对于每组测试数据：
第一行是三个正整数N,M,K（2<=N<=1000，1<=M<=N(N-1)/2，K<=10），分别表示节点数，边数和目标节点数。
接下来M行，每行三个整数u,v,w（1<=u,v<=N, 0<=w<=1000,u!=v）。如上所述给出每条传输线。任意两个网络节点之间最多只会有一条边相连。
最后一行是K个整数，给出所有的目标节点的编号，所有目标节点的编号都在2到N之间。

### 输出格式
对于每组测试数据，输出数据传送到所有K个目标节点的最短时间。

### 样例输入

```
2
3 2 2
1 3 1
1 2 3
2 3
6 6 4
1 5 1
5 6 2
2 1 20
2 3 5
3 4 5
6 3 1
2 3 4 6
```

### 样例输出

```
5
19
```

### 思路分析

这题我用的半天才AC...主要是调试太坑了。

* 正确理解题意。节点1只会发送一次数据。所以要求最短路径，其实是有一个**全排列**在里面的，找到合适的路径。
* 求最短路径，用弗洛伊德算法据说会超时，所以用k次的迪杰斯特拉算法
* 图的表示，我一开始是用三元组的集合来表示的，三元组即`start`、`end`、`weight`（权值），这种方式会导致**运行时错误问题**（内存超限，并不是某个数组或集合取数超限，而是内存超限），最后还是用邻接矩阵来表示图。

> java全排列

使用递归完成的。

### AC代码

```java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

public class Main {

public static Scanner scanner;

public static void main(String[] args) {
		scanner = new Scanner(System.in);
		int num = scanner.nextInt();
		for (int i = 0; i < num; i++) {
			Main network = new Main();
			network.handle();
		}
	}

public void handle() {
		MGraph mGraph = new MGraph();
		mGraph.vertexNum = scanner.nextInt();
		mGraph.edgesNum = scanner.nextInt();
		mGraph.tartgetVertexNum = scanner.nextInt();

mGraph.initEmptyDist();

for (int i = 0; i < mGraph.edgesNum; i++) {
			int start = scanner.nextInt();
			int end = scanner.nextInt();
			int weight = scanner.nextInt();
			
			mGraph.edges[start][end] = weight;
			mGraph.edges[end][start] = weight;
			
			mGraph.dist[start][end] = weight;
			mGraph.dist[end][start] = weight;
		}

for (int i = 0; i < mGraph.tartgetVertexNum; i++) {
			mGraph.tartgetVetexes.add(scanner.nextInt());
		}

mGraph.Dijkstra(1);

// output
		mGraph.calculateMinToTarger();

}

class MGraph {
		int vertexNum;
		int edgesNum;
		int tartgetVertexNum;

int[][] edges;
		List<Integer> tartgetVetexes = new ArrayList<Integer>();

int[][] dist;
		List<Integer> T = new ArrayList<Integer>();

int rootLength = -1;

public void initEmptyDist() {
			dist = new int[vertexNum + 1][vertexNum + 1];
			edges = new int[vertexNum + 1][vertexNum + 1];
			
			for (int i = 1; i <= vertexNum; i++) {
				for (int j = 1; j <= vertexNum; j++) {
					dist[i][j] = -1;
					edges[i][j] = -1;
				}
				
			}
		}

public void Dijkstra(int origin) {

// init vertexes data
			for (int i = 1; i <= vertexNum; i++) {
				if (i != origin) {
					T.add(i);
				}
			}

while (T.size() != 0) {
				int selectVertex = -1;
				int selectVertexInT = 0;

int min = -1;// position is not corrent in the past time
				for (int i = 0; i < T.size(); i++) {
					if (dist[origin][T.get(i)] != -1 && (dist[origin][T.get(i)] < min || min == -1)) {
						min = dist[origin][T.get(i)];
						selectVertex = T.get(i);
						selectVertexInT = i;
					}
				}
				// use this vertex to modify others dists

for (int i = 0; i < T.size(); i++) {
					int currentTargetVertex = T.get(i);
					int query = query(selectVertex, currentTargetVertex);
					if (query != -1) {
						int modified = min + query(selectVertex, currentTargetVertex);
						if (dist[origin][currentTargetVertex] == -1 || dist[origin][currentTargetVertex] > modified) {
							dist[origin][currentTargetVertex] = modified;
						}
					}
				}

T.remove(selectVertexInT);
			}
		}

public int query(int start, int end) {
			int result = -1;
			if (edges[start][end]!= -1) {
				result = edges[start][end];
			}
			return result;
		}

public void calculateMinToTarger() {
			for (int i = 0; i < tartgetVetexes.size(); i++) {
				Dijkstra(tartgetVetexes.get(i));
			}

permutation(tartgetVetexes, 0, tartgetVertexNum - 1);
			System.out.println(rootLength);

}

public void permutation(List<Integer> list, int from, int to) {
			if (to < from)
				return;
			if (from == to) {
				int tempRootLength = dist[1][list.get(0)];
				for (int i = 1; i < list.size(); i++) {
					tempRootLength += dist[list.get(i - 1)][list.get(i)];

}
				if (rootLength == -1 || rootLength > tempRootLength) {
					rootLength = tempRootLength;
				}

} else {
				for (int i = from; i <= to; i++) {
					swap(list, i, from);
					permutation(list, from + 1, to);
					swap(list, from, i);
				}
			}
		}

public void swap(List<Integer> s, int i, int j) {
			int tmp = s.get(i);
			s.set(i, s.get(j));
			s.set(j, tmp);
		}

}

class Edge{
		public int end;
		public int weight;
		
		public Edge() {
			// TODO 自动生成的构造函数存根
		}
		
		Edge(int end,int weight){
			this.end = end;
			this.weight = weight;
		}
		
	}

}
```

### 运行时错误问题的代码

```java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static Scanner scanner;
 
    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            Main network = new Main();
            network.handle();
        }
    }
 
    public void handle() {
        MGraph mGraph = new MGraph();
        mGraph.vertexNum = scanner.nextInt();
        mGraph.edgesNum = scanner.nextInt();
        mGraph.tartgetVertexNum = scanner.nextInt();
 
        mGraph.initEmptyDist();
 
        for (int i = 0; i < mGraph.edgesNum; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int weight = scanner.nextInt();
            mGraph.SGroups.add(new ThreeGronp(start, end, weight));
            mGraph.dist[start][end] = weight;
            mGraph.dist[end][start] = weight;
        }
 
        for (int i = 0; i < mGraph.tartgetVertexNum; i++) {
            mGraph.tartgetVetexes.add(scanner.nextInt());
        }
 
        mGraph.Dijkstra(1);
 
        // output
        mGraph.calculateMinToTarger();
 
    }
 
    class MGraph {
        int vertexNum;
        int edgesNum;
        int tartgetVertexNum;
 
        List<ThreeGronp> SGroups = new ArrayList<ThreeGronp>();// Information of
                                                                // edges
        List<Integer> tartgetVetexes = new ArrayList<Integer>();
 
        int[][] dist;
        List<Integer> T = new ArrayList<Integer>();
 
        int rootLength = -1;
 
        public void initEmptyDist() {
            dist = new int[vertexNum + 10][vertexNum + 10];
            for (int i = 1; i <= vertexNum; i++) {
                for (int j = 1; j <= vertexNum; j++) {
                    dist[i][j] = -1;
                }
            }
        }
 
        public void Dijkstra(int origin) {
 
            // init vertexes data
            for (int i = 1; i <= vertexNum; i++) {
                if (i != origin) {
                    T.add(i);
                }
            }
 
            while (T.size() != 0) {
                int selectVertex = -1;
                int selectVertexInT = 0;
 
                int min = -1;// position is not corrent in the past time
                for (int i = 0; i < T.size(); i++) {
                    if (dist[origin][T.get(i)] != -1 && (dist[origin][T.get(i)] < min || min == -1)) {
                        min = dist[origin][T.get(i)];
                        selectVertex = T.get(i);
                        selectVertexInT = i;
                    }
                }
                // use this vertex to modify others dists
 
                for (int i = 0; i < T.size(); i++) {
                    int currentTargetVertex = T.get(i);
                    int query = query(selectVertex, currentTargetVertex);
                    if (query != -1) {
                        int modified = min + query(selectVertex, currentTargetVertex);
                        if (dist[origin][currentTargetVertex] == -1 || dist[origin][currentTargetVertex] > modified) {
                            dist[origin][currentTargetVertex] = modified;
                        }
                    }
                }
 
                T.remove(selectVertexInT);
            }
        }
 
        public int query(int start, int end) {
            for (Iterator<ThreeGronp> iterator = SGroups.iterator(); iterator.hasNext();) {
                ThreeGronp threeGronp = (ThreeGronp) iterator.next();
                if ((threeGronp.start == start && threeGronp.end == end)
                        || (threeGronp.start == end && threeGronp.end == start)) {
                    return threeGronp.weight;
                }
            }
            return -1;
        }
 
        public void calculateMinToTarger() {
            for (int i = 0; i < tartgetVetexes.size(); i++) {
                Dijkstra(tartgetVetexes.get(i));
            }
 
            permutation(tartgetVetexes, 0, tartgetVertexNum - 1);
 
            System.out.println(rootLength);
 
        }
 
        public void permutation(List<Integer> list, int from, int to) {
            if (to < from)
                return;
            if (from == to) {
                int tempRootLength = dist[1][list.get(0)];
                for (int i = 1; i < list.size(); i++) {
                    tempRootLength += dist[list.get(i - 1)][list.get(i)];
 
                }
                if (rootLength == -1 || rootLength > tempRootLength) {
                    rootLength = tempRootLength;
                }
 
            } else {
                for (int i = from; i <= to; i++) {
                    swap(list, i, from);
                    permutation(list, from + 1, to);
                    swap(list, from, i);
                }
            }
        }
 
        public void swap(List<Integer> s, int i, int j) {
            int tmp = s.get(i);
            s.set(i, s.get(j));
            s.set(j, tmp);
        }
 
    }
 
    class ThreeGronp {
        int start;
        int end;
        int weight;
 
        public ThreeGronp(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
 
    }
 
}
```

> c++ 版本 指路 https://blog.csdn.net/TQCAI666/article/details/86765736

Problem A. 分数加法

题目描述

题目链接

求2-a + 2-b，其中a和b均为正整数，结果请用最简分数表示。

输入格式

第一行为测试数据的组数T（1<=T<=400）。请注意，任意两组测试数据之间是相互独立的。
每组测试数据一行，包含两个整数a和b（2<=a,b<=20）。

输出格式

对于每组测试数据，在一行内输出结果，分子和分母用“/”隔开。

输入样例

2
2 4
3 2

输出样例

5/16
3/8

思路解析

可能没考虑到是化简成最简分数。我一开始认为不可能需要化简呀！下面是偶数，上面是偶数+1一定是奇数，怎么还要化简呢...后来才发现，上面也可能是1+1，即a=b的情况

AC代码

package bupt;

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        
        for (int i = 0; i < num; i++) {
            int a = scanner.nextInt();
            int b =scanner.nextInt();
            
            int max= Math.max(a, b);
            int min = Math.min(a, b);
            
            int down = (int) Math.pow(2, max);
            int up = (int) Math.pow(2, max-min);
            up = up + 1;
            
            while (up%2==0){
                up/=2;
                down/=2;
            }// 比如 1/4 + 1/4 就需要化简成最简分数
            System.out.println(up + "/" + down);
        }
    }
}

Problem B. 最小堆

题目描述

题目链接

输入格式

输入数据第一行是一个整数T（1<=T<=100），表示测试数据的组数。
对于每组测试数据：
第一行是一个整数N（1<=N<=100），表示树的节点个数。
接下来一行包含N个正整数，第i个整数valuei(1<=valuei<=1000)表示编号i的点的权值。
接下来N-1行，每行两个整数u和v（1<=u，v<=N, u!=v），表示节点u是节点v的父节点。
测试数据保证给定的一定是一棵二叉树，并且节点1是树的根结点。

输出格式

对于每组测试数据，如果给定的树是一个最小堆则输出Yes，否则输出No。

输入样例

输出样例

Yes
No
Yes

思路解析

这题因为只是判断是不是最小堆，都不需要表示树，只要存储每个顶点的权值即可。然后边输入边变判断起点权值是否小于终点权值即可。
一般OJ题对普通树表示方法有父亲表示法（命名树一个节点只有一个父亲，偏偏叫双亲表示法，我服了），孩子表示法，孩子兄弟表示法。
对二叉树表示方法。

父亲表示法

就是一个一维数组，数组的元素序号表示顶点编号，值表示该顶点的父亲节点编号。

AC代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            int N = scanner.nextInt();//the number of vertexes;
            int[] vetexs = new int[101];
            
            for (int j = 1; j <= N; j++) {
                //input weight of vertexes
                vetexs[j] = scanner.nextInt();
            }
            
            boolean flag = true;
            for (int j = 0; j < N-1; j++) {
                //input relationship of edges
                int parent = scanner.nextInt();
                int child = scanner.nextInt();
                
                if (vetexs[parent] > vetexs[child]) {
                    if (flag) {
                        flag = false;
                    }
                }
            }
            if (flag) {
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }    
        scanner.close();
    }
}

Problem C. 进程管理

题目描述

题目链接

输入格式

输入的第一行是一个整数T（T<=50），表示输入的数据组数。
每组测试数据的第一行是一个整数N（1<=N<=100），表示操作的数量。
每下来N行，每行按照上面的描述给出每个操作，输入保证所有的进程的PID都不相同，且一个进程结束后不会被重新启动，所有PID都是[1,100]之间的整数。

输出格式

对于每次QUERY查询，如果进程存在，输出Yes，不存在则输出No

输入样例

2
5
FORK 0 1
QUERY 1
KILL 1
QUERY 1
QUERY 2
1
QUERY 0

输出样例

Yes
No
No
Yes

参考链接：BOJ 解题报告-268进程管理

思路解析

KILL 是本题的难点和坑的地方。KILL PID，子进程的子进程也需要KILL掉。所以一种方法每个进程有一个子进程列表的成员变量。在FORK的时候，就链式将当前进程沿着父进程的方向，加到沿途的每一个父进程的子进程列表中。（我是这么做的）另一个方法是KILL时候递归删除（没能理解！）
比如FORK 0 1的输入，因为java不能格式化输入，只能格式化输出。见下面具体说明。
list remove方法。remove(int index)与remove(Object o)这两个函数完全不同。第一个remove很好理解，按照索引删除。第二个是是将Object o 与List<Object>list使用equals函数进行循环匹配，所以必须重写equals函数。Object.equals(Object o)这个函数也有很多注意点。我暂且列举两篇文章：
- ArrayList的remove()方法
- 浅谈Java中的equals和==

（循环遍历删除某个元素，还可以用listIterater.remove()删除当前元素）

next()与nextLine()输入区别

nextInt()之类函数与next()特性一致。

next() 必须先进行有效输入（回车、换行、TAB、空格都是无效输入）才能结束输入（否则一直是等待输入的状态），然后再使用结束符号结束当前输入（回车、换行、TAB、空格的任一种）
nextLine()：就没有上面约束了，但是结束符号只有回车一个，所以可以输入含有空格的字符串。但是这个函数会接收回车符。

这两个函数的结束符号虽然都有一个回车\n，但是并不一样：

next() 回车后，\n 不会消失（要么被下一个next()过滤，要么被nextLine()接收），
nextLine() 回车后则会直接消失掉，所以下一个nextLine()可以正常接收输入，而不会接收到回车。

比如我先输入的5，其实输入的是5\n这个\n作为nextInt()结束符，但是\n 并不会消失，如果下面是nextLine() 就会被接收到。

所以本题在循环输入操作条件之前，先用下面一行接收掉没有消失的回车，再用nextLine()接收带有空格的操作字符串。最后用split(" ")分离字符串即可。

scanner.nextLine();//Receive enter symbol

AC代码

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;


public class Process {
    public static Scanner scanner;
    
    public List<Aprocess> list = new ArrayList<Aprocess>();

    
    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        int num  = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            Process process = new Process();
            process.handle();        
        }
    }
    
    public void handle(){
        int N = scanner.nextInt();
        list.add(new Aprocess("0","0"));
        scanner.nextLine();//Receive enter symbol
        for (int j = 0; j < N; j++) {
            String operation = scanner.nextLine();
            String[] array = operation.split(" ");
            if (array[0].equals("QUERY")) {
                int index = queryPidInList(array[1]);
                if (index != -1) {
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }else if (array[0].equals("FORK")) {
                forkPidInList(array[2],array[1]);
            }else if (array[0].equals("KILL")) {
                killPidInList(array[1]);
            }
        }
    }
    
    public int queryPidInList(String pid){
    
        for (ListIterator<Aprocess> iterator = list.listIterator(); iterator.hasNext();) {
            Aprocess aprocess = (Aprocess) iterator.next();
            if (pid.equals(aprocess.PID)) {
                return iterator.nextIndex() -1;
            }
        }
        return -1;
    }
    
    public void forkPidInList(String pid,String parent){
        int parentIndex = queryPidInList(parent);
        if (parentIndex != -1) {
            Aprocess newAprocess = new Aprocess(pid, parent);
            list.add(newAprocess);
            while(true){
                if (list.get(parentIndex).PID.equals("0")) {
                    break;
                }
                list.get(parentIndex).childPid.add(newAprocess);
                parentIndex = queryPidInList(list.get(parentIndex).parentPid);
            }
        }
        
    }
    
    
    public void killPidInList(String pid){
        if (!pid.equals("0")) {
            int pidIndex = queryPidInList(pid);
            if (pidIndex!=-1) {
                List<Aprocess> lStrings = list.get(pidIndex).childPid;
                for (Iterator<Aprocess> iterator = lStrings.iterator(); iterator.hasNext();) {
                    Aprocess aprocess = (Aprocess) iterator.next();
                    list.remove(aprocess);
                }
                list.remove(pidIndex);
            }        
        }
    }

    class Aprocess{
        String PID;
        String parentPid;
        List<Aprocess> childPid = new ArrayList<Aprocess>();
        
        public Aprocess() {
        }
        public Aprocess(String pid){
            this.PID = pid;
            this.parentPid = "0";
        }
        
        public Aprocess(String pid,String parent){
            this.PID = pid;
            this.parentPid = parent;
        }
        
        
        @Override
        public boolean equals(Object obj) {
            if (this.PID.equals(((Aprocess)obj).PID)) {
                return true;
            }
            return false;
        }
    }
}

Problem D. 网络传输

题目描述

题目链接

输入格式

输出格式

对于每组测试数据，输出数据传送到所有K个目标节点的最短时间。

样例输入

样例输出

5
19

思路分析

这题我用的半天才AC...主要是调试太坑了。

正确理解题意。节点1只会发送一次数据。所以要求最短路径，其实是有一个全排列在里面的，找到合适的路径。
求最短路径，用弗洛伊德算法据说会超时，所以用k次的迪杰斯特拉算法
图的表示，我一开始是用三元组的集合来表示的，三元组即start、end、weight（权值），这种方式会导致运行时错误问题（内存超限，并不是某个数组或集合取数超限，而是内存超限），最后还是用邻接矩阵来表示图。

java全排列

使用递归完成的。

AC代码

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static Scanner scanner;

    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            Main network = new Main();
            network.handle();
        }
    }

    public void handle() {
        MGraph mGraph = new MGraph();
        mGraph.vertexNum = scanner.nextInt();
        mGraph.edgesNum = scanner.nextInt();
        mGraph.tartgetVertexNum = scanner.nextInt();

        mGraph.initEmptyDist();

        for (int i = 0; i < mGraph.edgesNum; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int weight = scanner.nextInt();
            
            mGraph.edges[start][end] = weight;
            mGraph.edges[end][start] = weight;
            
            mGraph.dist[start][end] = weight;
            mGraph.dist[end][start] = weight;
        }

        for (int i = 0; i < mGraph.tartgetVertexNum; i++) {
            mGraph.tartgetVetexes.add(scanner.nextInt());
        }

        mGraph.Dijkstra(1);

        // output
        mGraph.calculateMinToTarger();

    }

    class MGraph {
        int vertexNum;
        int edgesNum;
        int tartgetVertexNum;

        int[][] edges;
        List<Integer> tartgetVetexes = new ArrayList<Integer>();

        int[][] dist;
        List<Integer> T = new ArrayList<Integer>();

        int rootLength = -1;

        public void initEmptyDist() {
            dist = new int[vertexNum + 1][vertexNum + 1];
            edges = new int[vertexNum + 1][vertexNum + 1];
            
            for (int i = 1; i <= vertexNum; i++) {
                for (int j = 1; j <= vertexNum; j++) {
                    dist[i][j] = -1;
                    edges[i][j] = -1;
                }
                
            }
        }

        public void Dijkstra(int origin) {

            // init vertexes data
            for (int i = 1; i <= vertexNum; i++) {
                if (i != origin) {
                    T.add(i);
                }
            }

            while (T.size() != 0) {
                int selectVertex = -1;
                int selectVertexInT = 0;

                int min = -1;// position is not corrent in the past time
                for (int i = 0; i < T.size(); i++) {
                    if (dist[origin][T.get(i)] != -1 && (dist[origin][T.get(i)] < min || min == -1)) {
                        min = dist[origin][T.get(i)];
                        selectVertex = T.get(i);
                        selectVertexInT = i;
                    }
                }
                // use this vertex to modify others dists

                for (int i = 0; i < T.size(); i++) {
                    int currentTargetVertex = T.get(i);
                    int query = query(selectVertex, currentTargetVertex);
                    if (query != -1) {
                        int modified = min + query(selectVertex, currentTargetVertex);
                        if (dist[origin][currentTargetVertex] == -1 || dist[origin][currentTargetVertex] > modified) {
                            dist[origin][currentTargetVertex] = modified;
                        }
                    }
                }

                T.remove(selectVertexInT);
            }
        }

        public int query(int start, int end) {
            int result = -1;
            if (edges[start][end]!= -1) {
                result = edges[start][end];
            }
            return result;
        }

        public void calculateMinToTarger() {
            for (int i = 0; i < tartgetVetexes.size(); i++) {
                Dijkstra(tartgetVetexes.get(i));
            }

            permutation(tartgetVetexes, 0, tartgetVertexNum - 1);
            System.out.println(rootLength);

        }

        public void permutation(List<Integer> list, int from, int to) {
            if (to < from)
                return;
            if (from == to) {
                int tempRootLength = dist[1][list.get(0)];
                for (int i = 1; i < list.size(); i++) {
                    tempRootLength += dist[list.get(i - 1)][list.get(i)];

                }
                if (rootLength == -1 || rootLength > tempRootLength) {
                    rootLength = tempRootLength;
                }

            } else {
                for (int i = from; i <= to; i++) {
                    swap(list, i, from);
                    permutation(list, from + 1, to);
                    swap(list, from, i);
                }
            }
        }

        public void swap(List<Integer> s, int i, int j) {
            int tmp = s.get(i);
            s.set(i, s.get(j));
            s.set(j, tmp);
        }

    }

    class Edge{
        public int end;
        public int weight;
        
        public Edge() {
            // TODO 自动生成的构造函数存根
        }
        
        Edge(int end,int weight){
            this.end = end;
            this.weight = weight;
        }
        
    }

}

运行时错误问题的代码

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static Scanner scanner;
 
    public static void main(String[] args) {
        scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        for (int i = 0; i < num; i++) {
            Main network = new Main();
            network.handle();
        }
    }
 
    public void handle() {
        MGraph mGraph = new MGraph();
        mGraph.vertexNum = scanner.nextInt();
        mGraph.edgesNum = scanner.nextInt();
        mGraph.tartgetVertexNum = scanner.nextInt();
 
        mGraph.initEmptyDist();
 
        for (int i = 0; i < mGraph.edgesNum; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int weight = scanner.nextInt();
            mGraph.SGroups.add(new ThreeGronp(start, end, weight));
            mGraph.dist[start][end] = weight;
            mGraph.dist[end][start] = weight;
        }
 
        for (int i = 0; i < mGraph.tartgetVertexNum; i++) {
            mGraph.tartgetVetexes.add(scanner.nextInt());
        }
 
        mGraph.Dijkstra(1);
 
        // output
        mGraph.calculateMinToTarger();
 
    }
 
    class MGraph {
        int vertexNum;
        int edgesNum;
        int tartgetVertexNum;
 
        List<ThreeGronp> SGroups = new ArrayList<ThreeGronp>();// Information of
                                                                // edges
        List<Integer> tartgetVetexes = new ArrayList<Integer>();
 
        int[][] dist;
        List<Integer> T = new ArrayList<Integer>();
 
        int rootLength = -1;
 
        public void initEmptyDist() {
            dist = new int[vertexNum + 10][vertexNum + 10];
            for (int i = 1; i <= vertexNum; i++) {
                for (int j = 1; j <= vertexNum; j++) {
                    dist[i][j] = -1;
                }
            }
        }
 
        public void Dijkstra(int origin) {
 
            // init vertexes data
            for (int i = 1; i <= vertexNum; i++) {
                if (i != origin) {
                    T.add(i);
                }
            }
 
            while (T.size() != 0) {
                int selectVertex = -1;
                int selectVertexInT = 0;
 
                int min = -1;// position is not corrent in the past time
                for (int i = 0; i < T.size(); i++) {
                    if (dist[origin][T.get(i)] != -1 && (dist[origin][T.get(i)] < min || min == -1)) {
                        min = dist[origin][T.get(i)];
                        selectVertex = T.get(i);
                        selectVertexInT = i;
                    }
                }
                // use this vertex to modify others dists
 
                for (int i = 0; i < T.size(); i++) {
                    int currentTargetVertex = T.get(i);
                    int query = query(selectVertex, currentTargetVertex);
                    if (query != -1) {
                        int modified = min + query(selectVertex, currentTargetVertex);
                        if (dist[origin][currentTargetVertex] == -1 || dist[origin][currentTargetVertex] > modified) {
                            dist[origin][currentTargetVertex] = modified;
                        }
                    }
                }
 
                T.remove(selectVertexInT);
            }
        }
 
        public int query(int start, int end) {
            for (Iterator<ThreeGronp> iterator = SGroups.iterator(); iterator.hasNext();) {
                ThreeGronp threeGronp = (ThreeGronp) iterator.next();
                if ((threeGronp.start == start && threeGronp.end == end)
                        || (threeGronp.start == end && threeGronp.end == start)) {
                    return threeGronp.weight;
                }
            }
            return -1;
        }
 
        public void calculateMinToTarger() {
            for (int i = 0; i < tartgetVetexes.size(); i++) {
                Dijkstra(tartgetVetexes.get(i));
            }
 
            permutation(tartgetVetexes, 0, tartgetVertexNum - 1);
 
            System.out.println(rootLength);
 
        }
 
        public void permutation(List<Integer> list, int from, int to) {
            if (to < from)
                return;
            if (from == to) {
                int tempRootLength = dist[1][list.get(0)];
                for (int i = 1; i < list.size(); i++) {
                    tempRootLength += dist[list.get(i - 1)][list.get(i)];
 
                }
                if (rootLength == -1 || rootLength > tempRootLength) {
                    rootLength = tempRootLength;
                }
 
            } else {
                for (int i = from; i <= to; i++) {
                    swap(list, i, from);
                    permutation(list, from + 1, to);
                    swap(list, from, i);
                }
            }
        }
 
        public void swap(List<Integer> s, int i, int j) {
            int tmp = s.get(i);
            s.set(i, s.get(j));
            s.set(j, tmp);
        }
 
    }
 
    class ThreeGronp {
        int start;
        int end;
        int weight;
 
        public ThreeGronp(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
 
    }
 
}

c++ 版本指路 https://blog.csdn.net/TQCAI666/article/details/86765736

最后修改：2019 年 03 月 01 日

喜欢我的文章吗？
别忘了点赞或赞赏，让我知道创作的路上有你陪伴。

Problem A. 分数加法

题目描述

输入格式

输出格式

输入样例

输出样例

思路解析

AC代码

Problem B. 最小堆

题目描述

输入格式

输出格式

输入样例

输出样例

思路解析

AC代码

Problem C. 进程管理

题目描述

输入格式

输出格式

输入样例

输出样例

思路解析

AC代码

Problem D. 网络传输

题目描述

输入格式

输出格式

样例输入

样例输出

思路分析

AC代码

运行时错误问题的代码

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

北邮2014年网研机试

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款