首页 > 试题广场 >

情报

[编程题]情报
  • 热度指数：734 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
Brotherhood在KWAI建立了分部，但由于燕大人杰地灵，不是什么人都能够任意进出的，于是现在一个棘手的问题摆在了Ezio面前：情报的传递。

已知燕大内的Brotherhood一共有 n 个团体，有些团体之间有一些关系，你可以把它们看作一条边，每条边连接了两个 **不同** 的团体，现在一共有 m 条边。

现在前辈 Jumbo 要求 Ezio 将一个情报传递给燕大内的所有团体。已知 Ezio 亲自去向团体i告知情报的代价为 val[i] 。Ezio 当然不想一个一个去找啦，他还有很多任务要完成，于是他发现他可以利用团体之间的关系，让某一个已经被传达过情报的团体去告知另一与之有关系团体。

但是团体内部的人懒癌发作，自然不想白白地去帮 Ezio跑 腿。具体来说，针对关系 (u,v) ，如果 Ezio 想要利用它，应该付出的代价为cost(u,v)。

简而言之：
一个团体得到情报有两种方式：
1.由 Ezio 亲自告知，即代价为 val[i]。
2.由一个与之有关系且已经得到情报的团体以 cost(u,v) 为代价得到情报。

现在 Ezio 想要花费最少的代价让所有团体得到情报，你能帮帮他吗？

输入的第一行表示测试数据组数，满足  

数据范围：每组测试用例满足 ，

输入描述:
第一行一个整数t(1 <= t <= 5)，表示测试用例组数。

对于每组测试用例：

第一行两个用空格隔开的整数n和m(1 <= n, m <= 100000)，分别表示团体个数和关系数量。

接下来一行n个用空格隔开的数，第i个数表示val[i]。

接下来m行，每行三个用空格隔开的整数u,v和cost(u,v)(1 <= u, v <= n,  1 <= val[i], cost(u, v) <= 20000)。


输出描述:
对于每组测试用例，你的程序需要输出一行一个整数表示询问的答案。
示例1

输入

2
5 8
2 8 5 1 10
1 2 5
1 3 9
3 4 5
2 5 6
3 2 2
1 3 8
5 3 4
4 1 8
5 8
7 2 9 10 3
1 2 8
1 3 6
1 4 4
2 5 3
4 5 2
2 4 9
3 5 3
5 4 2

输出

14
14
算法知识视频讲解
添加回答
Java
MC枫少头像 MC枫少
亲测可用：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
 
/**
 * @Author: coderjjp
 * @Date: 2020-05-10 14:28
 * @Description: 情报
 * @version: 1.0
 */
class Edge{
    int from, to, val;
    public Edge(int from, int to, int val) {
        this.from = from;
        this.to = to;
        this.val = val;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0){
            String[] line1 = br.readLine().split(" ");
            int n = Integer.parseInt(line1[0]);//除0以外的顶点数
            int m = Integer.parseInt(line1[1]);//除0以外的其他顶点关系数
            ArrayList<Edge> edges = new ArrayList<>(); //存储所有的边
            String[] line2 = br.readLine().split(" ");
            for (int i = 1; i <= n; i++)
                edges.add(new Edge(0, i, Integer.parseInt(line2[i-1])));
            for (int i = 0; i < m; i++){
                String[] line = br.readLine().split(" ");
                edges.add(new Edge(Integer.parseInt(line[0]), Integer.parseInt(line[1]), Integer.valueOf(line[2])));
            }
            edges.sort(Comparator.comparingInt(o -> o.val));
            int p[] = new int[n+1];
            for (int i = 0; i <= n; i++)
                p[i] = i;
            int ans = GenTree(m+n, n+1, edges, p);
            System.out.println(ans);
        }
    }
    private static int findParent(int i, int[] p){
        if(i!=p[i])
            p[i]=findParent(p[i], p);
        return p[i];
    }
 
    private static int GenTree(int len, int n, ArrayList<Edge> edges, int[] p){
        int sum=0,num=0;
        for(int i=0;i<len&&num<n-1;i++){
            int ps=findParent(edges.get(i).from, p);
            int pe=findParent(edges.get(i).to, p);
            if(pe!=ps){
                p[pe]=ps;
                num++;
                sum+=edges.get(i).val;
            }
        }
        return sum;
    }
}

发表于 2022-07-02 09:40:14 回复(0)
Java
ADPX丶头像 ADPX丶 
import java.util.*;

public class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int total = sc.nextInt();

        for (int i = 0; i < total; i++) {
            
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] values = new int[n];
            int[][] edgesInfo = new int[m][3];
            for (int j = 0; j < n; j++)
                values[j] = sc.nextInt();
            //System.out.println(Arrays.toString(values));
            
            for (int j = 0; j < m; j++) {
                edgesInfo[j][0] = sc.nextInt();
                edgesInfo[j][1] = sc.nextInt();
                edgesInfo[j][2] = sc.nextInt();
            }
            //System.out.println(Arrays.deepToString(edgesInfo));
            int minCost = minCost(n,values,edgesInfo);
            System.out.println(minCost);
       }
    }
    
    public static int minCost(int n, int[] vals, int[][] edgesInfo){

        Graph graph = new Graph(n + 1);
        for (int i = 0; i < vals.length; i++)
            graph.setEdge(0,i + 1,vals[i]);

        for (int i = 0; i < edgesInfo.length; i++)
            graph.setEdge(edgesInfo[i][0],edgesInfo[i][1],edgesInfo[i][2]);

        return graph.spt();
    }


    private static class Graph{
        ArrayList<Edge> edges;
        private int num;

        Graph(int num){
            this.num = num;
            edges = new ArrayList<>();
        }

        /**
         * 设置边
         */
        public void setEdge(int from, int to, int cost){

            // 创建边
            Edge edge = new Edge(from,to,cost);
            edges.add(edge);
        }

        /**
         * 最小生成树
         */
        public int spt(){

            int ans = 0;
            PriorityQueue<Edge> heap = new PriorityQueue<>();
            heap.addAll(edges);
            int count = 0;
            // 并查集
            Union union = new Union(num);

            while(count < num && !heap.isEmpty()){

                Edge edge = heap.poll();
                if(union.isSame(edge.to,edge.from)) continue;
                ans += edge.cost;
                ++count;
                union.union(edge.from, edge.to);
            }
            return ans;
        }

    }

    static class Edge implements Comparable<Edge>{
        int from;
        int to;
        int cost;

        Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge node) {
            return this.cost - node.cost;
        }
    }
}

/**
 * 并查集
 *    基于 rank 优化和 路径分裂 优化的并查集
 */
class Union {

    private int[] parent;
    private int[] rank;

    public Union(int capacity){
        if(capacity <= 0) throw new IllegalArgumentException("capacity must be >= 1");
        parent = new int[capacity];
        rank = new int[capacity];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    private boolean rangeCheck(int k){
        if(k >= parent.length || k < 0) throw new IllegalArgumentException("unVaild arguments k" + k);
        return true;
    }

    /**
     * 合并两个集合
     */
    public void union(int v1, int v2){

        int p1 = find(v1);
        int p2 = find(v2);
        if(p1 == p2) return;

        // 如果 p1 高度较大，将 p2 合并到 p1 上。
        // 如果 p2 高度较大，将 p1 合并到 p2 上。
        if(rank[p1] > rank[p2])
            parent[p2] = p1;
        else if(rank[p1] < rank[p2])
            parent[p1] = p2;
        else {
            parent[p1] = p2;
            ++rank[p1];
        }
    }


    /**
     * 在 find 时，将路径上的每个节点都指向其祖父节点
     */
    public int find(int v){

        rangeCheck(v);
        while(v != parent[v]) {
            int v_parent = parent[v];
            // 当前节点指向其祖父节点
            parent[v] = parent[parent[v]];
            v = v_parent;
        }
        return v;
    }

    public boolean isSame(int v1, int v2){
        return find(v1) == find(v2);
    }
}

编辑于 2020-07-10 22:23:48 回复(0)
Java
何止hz头像 何止hz
本质是求最小生成树，加边法Java实现如下。尝试用纯数组、边数组，边集合进行保存边数据，最后就边集合方式AC了，其他都超时了。 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 14:28
 * @Description: 情报
 * @version: 1.0
 */
class Edge{
    int from, to, val;
    public Edge(int from, int to, int val) {
        this.from = from;
        this.to = to;
        this.val = val;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0){
            String[] line1 = br.readLine().split(" ");
            int n = Integer.parseInt(line1[0]);//除0以外的顶点数
            int m = Integer.parseInt(line1[1]);//除0以外的其他顶点关系数
            ArrayList<Edge> edges = new ArrayList<>(); //存储所有的边
            String[] line2 = br.readLine().split(" ");
            for (int i = 1; i <= n; i++)
                edges.add(new Edge(0, i, Integer.parseInt(line2[i-1])));
            for (int i = 0; i < m; i++){
                String[] line = br.readLine().split(" ");
                edges.add(new Edge(Integer.parseInt(line[0]), Integer.parseInt(line[1]), Integer.valueOf(line[2])));
            }
            edges.sort(Comparator.comparingInt(o -> o.val));
            int p[] = new int[n+1];
            for (int i = 0; i <= n; i++)
                p[i] = i;
            int ans = GenTree(m+n, n+1, edges, p);
            System.out.println(ans);
        }
    }
    private static int findParent(int i, int[] p){
        if(i!=p[i])
            p[i]=findParent(p[i], p);
        return p[i];
    }

    private static int GenTree(int len, int n, ArrayList<Edge> edges, int[] p){
        int sum=0,num=0;
        for(int i=0;i<len&&num<n-1;i++){
            int ps=findParent(edges.get(i).from, p);
            int pe=findParent(edges.get(i).to, p);
            if(pe!=ps){
                p[pe]=ps;
                num++;
                sum+=edges.get(i).val;
            }
        }
        return sum;
    }
}


发表于 2020-05-10 17:06:07 回复(0)
提交观点

问题信息

动态规划 快手 算法工程师 图 2019 递归
上传者：小小
难度：
3条回答 5786浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号