首页 > 代码库 > 国王的烦恼
国王的烦恼
描述
C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起发起抗议。
现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们一共会发起多少次抗议。
- 输入
- 多组测试数据。
每组数据先输入两个正整数n和m。
接下来m行，每行三个整数a, b, t，分别表示该座桥连接a号和b号两个小岛，能使用t天。小岛的编号从1开始递增。（1≤n≤10000,1≤m≤100000，1<=a,b<=n，1≤t≤100000） - 输出
- 输出一个整数，表示居民们发起抗议的次数。
- 样例输入
4 41 2 21 3 22 3 13 4 3
- 样例输出
2
- 提示
- 对于样例：
第一天后2和3之间的桥不能使用，不影响。
第二天后1和2之间，以及1和3之间的桥不能使用，居民们会抗议。
第三天后3和4之间的桥不能使用，居民们会抗议。 package com.Major;import java.util.*;public class Main{ static HashSet<Integer> f=new HashSet<Integer>(); static List<Integer> x=new ArrayList<Integer>(); static int n=0; public static void main(String vgs[]) throws Exception{ Scanner sn=new Scanner(System.in); String line=sn.nextLine(); n=Integer.valueOf(line.split(" ")[0]); int m=Integer.valueOf(line.split(" ")[1]); List<Brg> brg=new ArrayList<Brg>(); for(int i=0;i<m;i++){ String[] str=sn.nextLine().split(" "); int a=Integer.valueOf(str[0]); int b=Integer.valueOf(str[1]); int date=Integer.valueOf(str[2]); Brg bg=new Brg(a,b,date); brg.add(bg); } x.add(1);//从第一个岛开始取 while(x.size()<n){//判断是否所有小岛都已经取到 Prim(brg,x); } System.out.println(f.size()); } public static void Prim(List<Brg> brg,List<Integer> a){ int d=0; int n=0; Brg bbb=new Brg(); //按最大边提取岛 从编号为1的岛开始取，从这个岛与别的联通的岛中，取出桥存在时间最长的那个岛x //把这个岛x放入岛的集合a中，同时brg中去掉已经去掉的岛，重复，直到所有的岛都取出来为止 for(int i=0;i<a.size();i++){ for(Brg brg1:brg){ if(brg1.getA()==a.get(i)){ if(d<brg1.getDate()){ n=brg1.getB(); d=brg1.getDate(); bbb=brg1; } }else if(brg1.getB()==a.get(i)){ if(d<brg1.getDate()){ n=brg1.getA(); d=brg1.getDate(); bbb=brg1; } } } } //判断是否取到值（存在小岛） if(d!=0){ brg.remove(bbb); f.add(d); x.add(n); } }}class Brg{ private int a; private int b; private int date; public Brg(int a,int b,int date){ this.a=a; this.b=b; this.date=date; } public Brg() { // TODO Auto-generated constructor stub } public void setA(int a){ this.a=a; } public int getA(){ return this.a; } public void setB(int b){ this.b=b; } public int getB(){ return this.b; } public void setDate(int date){ this.date=date; } public int getDate(){ return this.date; }}
我使用的是prim算法，但是提交结果是TimeLimitExceeded，暂时没想到优化方案。
国王的烦恼
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。