首页 > 试题广场 >

紧急疏散

[编程题]紧急疏散

热度指数：2232 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

体育场突然着火了，现场需要紧急疏散，但是过道真的是太窄了，同时只能容许一个人通过。现在知道了体育场的所有座位分布，座位分布图是一棵树，已知每个座位上都坐了一个人，安全出口在树的根部，也就是1号结点的位置上。其他节点上的人每秒都能向树根部前进一个结点，但是除了安全出口以外，没有任何一个结点可以同时容纳两个及以上的人，这就需要一种策略，来使得人群尽快疏散，问在采取最优策略的情况下，体育场最快可以在多长时间内疏散完成。

数据范围： $1 \le n \le 10^5 \$

输入描述:

第一行包含一个正整数n，即树的结点数量。 接下来有n-1行，每行有两个正整数x，y，表示在x和y结点之间存在一条边。(1<=x，y<=n)

输出描述:

输出仅包含一个正整数，表示所需要的最短时间

示例1

输入

输出

算法知识视频讲解

Java

何止hz

一开始没看清题目，以为出口只能容纳俩人呢。其实就是求出根节点的各个子树的节点个数的最大值就是最终答案，节点遍历的基础问题，可以采用bfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: coderjjp
 * @Date: 2020-05-12 8:46
 * @Description: 紧急疏散
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n - 1; i++){
            String line[] = br.readLine().split(" ");
            int f = Integer.parseInt(line[0]);
            int t = Integer.parseInt(line[1]);
            if (!graph.containsKey(f))
                graph.put(f, new ArrayList<>());
            if (!graph.containsKey(t))
                graph.put(t, new ArrayList<>());
            graph.get(f).add(t);
            graph.get(t).add(f);
        }
        Queue<Integer> queue = new LinkedList<>();
        boolean flag[] = new boolean[n+1];
        ArrayList<Integer> subNode = new ArrayList<>();
        flag[1] = true;
        int res = 0;
        //得到次子节点
        if (graph.containsKey(1))
            for(Integer it: graph.get(1)){
                subNode.add(it);
                flag[it] = true;
            }
        //遍历次子节点分别求子树节点个数
        for(int i = 0; i < subNode.size();i++){
            queue.offer(subNode.get(i));
            int num = 0;
            while(!queue.isEmpty()){
                int tem = queue.poll();
                num++;
                flag[tem] = true;
                if (graph.get(tem) != null)
                    for (int nextNode: graph.get(tem)){
                        if (!flag[nextNode]){
                            queue.offer(nextNode);
                            flag[nextNode] = true;
                        }
                    }
            }
            res = Math.max(res, num);
        }
        System.out.println(res);
    }
}

发表于 2020-05-12 16:16:34 回复(0)

Java

Rhinocero

搞个并查集，给并查集附带一个isolate方法，意义是在union过程中如果发现union的节点双方有一个是1的话就不继续union，并将另一个节点和头结点原地互换（在这里用哈希表直接换索引内容），继而会得到k个并查集，其中一个只有1本身，另外k-1个分别是直接与1相连的节点为头部的子集们，返回size最大的即为最大需要时间。

感觉这个方法空间上不是很优，希望有大佬看到的话给点建议好啦

import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static class ufsNode{
        int id;
        public ufsNode(int id){this.id = id;}
    }

    public static class UFS{
        HashMap<ufsNode,ufsNode> father;
        HashMap<ufsNode,Integer> size;
        HashMap<Integer,ufsNode> index;

        public UFS(int nodeNum){
            father = new HashMap<>();
            size = new HashMap<>();
            index =  new HashMap<>();

            for (int i = 1; i < nodeNum+1; i++) {
                ufsNode node = new ufsNode(i);
                index.put(i,node);
                father.put(node,node);
                size.put(node,1);
            }
        }

        public ufsNode find(ufsNode n){
            ufsNode f = father.get(n);
            if(n!=f)
                return find(f);
            father.put(n,f);
            return f;
        }

        public void isolate(ufsNode node){
            ufsNode head = find(node);
            if(node!=head){
                int curNum = node.id;
                int headNum = head.id;
                head.id = curNum;
                node.id = headNum;
                index.put(curNum,head);
                index.put(headNum,node);
            }
        }

        public void union(int a,int b){
            ufsNode nodeA = index.get(a);
            ufsNode nodeB = index.get(b);
            if(a==1) {
                isolate(nodeB);
                return;
            }
            if(b==1) {
                isolate(nodeA);
                return;
            }

            ufsNode aHead = find(nodeA);
            ufsNode bHead = find(nodeB);
            if(aHead==bHead)
                return;
            if(size.get(aHead)<=size.get(bHead)){
                father.put(aHead,bHead);
                size.put(bHead,size.get(aHead)+size.get(bHead));
            }else{
                father.put(bHead,aHead);
                size.put(aHead,size.get(aHead)+size.get(bHead));
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size=0;
        if(sc.hasNextInt())
            size = sc.nextInt();
        UFS ufs = new UFS(size);
        while(sc.hasNextInt()){
            ufs.union(sc.nextInt(),sc.nextInt());
        }
        int res = 0;
        for (int i = 2; i < size+1; i++) {
            res = Math.max(res,ufs.size.get(ufs.index.get(i)));
        }
        System.out.println(res);

    }

}

发表于 2020-03-17 18:10:23 回复(0)