首页 > 试题广场 >

情报

[编程题]情报
  • 热度指数:733 时间限制: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
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)
#include <bits/stdc++.h>
using namespace std;

const int N = 1000003;
int val[N], p[N];
struct Edge{
    int u,v,w;
    bool operator < (const Edge &e){
        return w < e.w;
    }
}E[N*2];

int FindParent(int x){
    if(x!=p[x])
        p[x] = FindParent(p[x]);
    return p[x];
}

int main(){
    int t, n, m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>val[i];
        for(int i=1;i<=m;i++)
            cin>>E[i].u>>E[i].v>>E[i].w;
        for(int i=1;i<=n;i++){
            E[m+i].u = n+1;
            E[m+i].v = i;
            E[m+i].w = val[i];
        }
        n++;
        sort(E+1, E+n+m+1);
        int r = 0;
        for(int i=1;i<=n+m;i++)
            p[i] = i;
        for(int i=1,cnt=0;i<=n+m && cnt<n-1;i++){
            int fu = FindParent(E[i].u);
            int fv = FindParent(E[i].v);
            if(fu != fv){
                p[fv] = fu;
                r += E[i].w;
                cnt++;
            }
        }
        cout<<r<<endl;
    }
    return 0;
}

发表于 2020-01-20 01:54:53 回复(1)
***玩意
发表于 2023-07-27 17:29:50 回复(0)
亲测可用:
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)
测试用例里  1 3 8和1 3 9是什么情况
发表于 2020-11-16 21:15:04 回复(0)
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
//最小生成树,Prim算法
public class Main{
  public static void main(String[] args)throws IOException{
    //用Scanner竟然超时
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while(--t>=0){
    	String [] strs = br.readLine().split(" ");
        int m = Integer.parseInt(strs[0]);
        int n = Integer.parseInt(strs[1]);
        Edge[] edges = new Edge[n+m];
        strs = br.readLine().split(" ");
        for(int i=0; i<m; i++){
            edges[i] = new Edge(i+1,m+1,Integer.parseInt(strs[i]));
        }
        for(int i=m; i<m+n; i++){
        	strs = br.readLine().split(" ");
            edges[i] = new Edge(Integer.parseInt(strs[0]),Integer.parseInt(strs[1]),Integer.parseInt(strs[2]));
        }
        Arrays.sort(edges);
        int p[] = new int[m+1];
        for(int i=0;i<=m;i++){
            p[i]=i;
        }
        int cost = 0;
        for(int i=0,cnt=0;i<m+n && cnt<m;i++){
            int fu = findParant(p,edges[i].u-1);
            int fv = findParant(p,edges[i].v-1);
            if(fv!=fu){
                p[fv]=fu;
                cost+=edges[i].w;
                cnt++;
            }
        }
        System.out.println(cost);
    }
}
  public static int findParant(int[] p,int v){
      if(p[v]!=v){
          p[v] = findParant(p,p[v]);
      }
      return p[v];
  }
}
class Edge implements Comparable<Edge>{
  int u;
  int v;
  int w;
  Edge(int u,int v,int w){
      this.u = u;
      this.v = v;
      this.w = w;
  }
  @Override
  public int compareTo(Edge edge){
      return this.w-edge.w;
  }
}

发表于 2020-08-10 19:49:15 回复(0)
import java.util.*;
import java.lang.*;
class Edge implements Comparable{
    int u,v,w;
    public Edge(int u,int v,int w){
        this.u = u;
        this.v = v;
        this.w = w;
    }
    @Override
    public int compareTo(Object o){
        Edge e = (Edge)o;
        return this.w-e.w;
    }
}
public class Main{
    private static Map<Integer,Integer>map = new HashMap<>();
    private static int[] father;
    public static void main(String[] args){
        int t,n,m;
        Scanner scan = new Scanner(System.in);
        t = Integer.parseInt(scan.nextLine());
        while(t-->0){
            map.clear();
            String line = scan.nextLine();
            String[] list = line.split(" ");
            n = Integer.parseInt(list[0]);
            m = Integer.parseInt(list[1]);
//            System.out.println(n);
//            System.out.println(m);
            List<Edge>edges = new ArrayList<>();
            for(int i=1;i<=n;++i){
                int dis = scan.nextInt();
                edges.add(new Edge(0,i,dis));
            }
            String ss = scan.nextLine();
            for(int i=1;i<=m;++i){
                String strs = scan.nextLine();
                String[] str = strs.split(" ");
                edges.add(new Edge(Integer.parseInt(str[0]),Integer.parseInt(str[1]),Integer.parseInt(str[2])));
            }
            Collections.sort(edges);
//            for(Edge e:edges)
//                System.out.println(e.w);
            father = new int[n+1];
            for(int i=0;i<=n;++i)
            {
                father[i] = i;
                map.put(i,1);
            }
            int cnt = 0;
            int ans = 0;
            for(Edge edge:edges){
                if(cnt>=n)
                    break;
                if(Union(edge.u,edge.v)){
                    cnt++;
                    ans+=edge.w;
                }
            }
            System.out.println(ans);
        }
    }
    private static int find(int x){
        int t = x;
        while(x!= father[x])
            x = father[x];
        // 路径压缩
        while(t!=x){
            int a = father[t];
            father[t] = x;
            t = a;
        }
        return x;
    }
    private static Boolean Union(int x,int y){
        int fa_x = find(x);
        int fa_y = find(y);
        if(fa_x!=fa_y)
        {
            int rank_x = map.get(fa_x);
            int rank_y = map.get(fa_y);
            int big = rank_x>rank_y ? fa_x:fa_y;
            int small = big==fa_x ? fa_y:fa_x;
            father[small] = big;
            map.put(big,map.get(fa_y)+map.get(fa_x));
            map.remove(small);
            return true;
        }
        return false;
    }

}
发表于 2020-07-02 16:01:31 回复(1)
本质是求最小生成树,加边法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)