[华为机试]朋友圈信息转发

朋友圈转发信息

描述:

在一个社交应用中，两个用户设定朋友关系后，则可以互相收到对方发布或转发的信息。当一个用户发布或转发一条信息时，他的所有朋友都能收到该信息。

现给定一组用户，及用户之间的朋友关系。

问：当某用户发布一条信息之后，为了让每个人都能在最早时间收到这条信息，这条信息最少需要被转发几次？

假设：对所有用户而言：

1）朋友发出信息到自己收到该信息的时延为T（T>0）；

2）如需转发，从收到信息到转发出信息的时延为0。

用例保证：在给定的朋友圈关系中，，任何人发布的信息总是能通过N（N>=0）次转发让其他所有用户收到。

例如：

下图表示某个朋友圈关系（节点间连线表示朋友关系）中，用户1在时刻0发布信息之后，两种不同的转发策略。

黄色节点表示转发用户，蓝色数字为用户收到信息的时间。

运行时间限制:无限制

内存限制:无限制

输入:

Sender

[消息创建者编号]

Relationship

[朋友关系列表，1,2表示1和2是朋友关系]

End

如下：

Sender1Relationship1,21,31,42,52,63,64,64,75,65,85,96,76,86,97,910,7End

输出:

当某用户发布一条信息之后，为了让每个人都能在最早时间收到这条信息，这条信息最少需要被转发的次数

样例输入:Sender1Relationship1,21,31,42,52,63,64,64,75,65,85,96,76,86,97,910,7End

样例输出:4

答案提示:

可以发现，每个用户接受到信息的时间，是他到起点（消息创建者编号）消息创建着的最短路，故先用最短路预处理。

然后可以发现，收到消息时间为 T 的用户是否选择发布消息，只会影响到 2T的用户，（因为，时间T的用户的儿子一定是时间为2T的用户，因为每个人都要最早收到消息），而影响不到3T、4T……的用户。 类似的，2T用户的决策影响3T用户。

那么，问题就简化成选最少的上层用户，让下层每个用户都收到最早消息，也就是一个二分图问题。

从u到v，要求能到达v的每一点，u中需要的最小点数

（以上分析摘自我的牛逼师弟）

然后利用二分答案求解即可

package 朋友圈转发消息;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.LinkedHashSet;import java.util.LinkedList;import java.util.List;import java.util.Map;import java.util.Queue;import java.util.Scanner;import java.util.Set;class Node {@Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + val;return result;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;Node other = (Node) obj;if (val != other.val)return false;return true;}int val;Node(int val) {this.val = val;}List<Node> next = new ArrayList<>();}public class Main {static Map<Integer, Node> map = new HashMap<>();static Set<Node> used = new HashSet<>();static int res = 0;public static void bfs(int sender){Queue<Node> que = new LinkedList<>();Queue<Node> next = new LinkedList<>();Node seed = map.get(sender);que.add(seed);used.add(seed);while (!que.isEmpty()) {List<Node> father = new ArrayList<>();List<Node> son = new ArrayList<>();Map<Integer,Node> mapSon = new HashMap<>();List<Node> listUse = new ArrayList<>();while (!que.isEmpty()) {Node n = que.poll();Node fa = new Node(n.val);father.add(fa);List<Node> list = n.next;for (Node node : list) {if (used.contains(node))continue;listUse.add(node);Node so;if(mapSon.containsKey(node.val)){so= mapSon.get(node.val);}else{next.add(node);so = new Node(node.val);son.add(so);mapSon.put(node.val, so);}fa.next.add(so);so.next.add(fa);}}for(Node node:listUse){used.add(node);}// /////bGraph(father, son);Queue<Node> lin = que;que = next;next = lin;}}private static void bGraph(List<Node> father, List<Node> son) {if(father.size()==1||son.size()==1) {res +=1;return;}if(son.size()==0) return;int left =1,right = father.size();int mid = (left+right)/2;while(mid<right){can = false;sonUsed.clear();bGraph(father, son, 0, 0, mid);if (can) {right = mid;} else {left = mid+1;}} res +=mid;return;}static Set<Node> sonUsed = new LinkedHashSet<>();static boolean can = false;private static void bGraph(List<Node> father,List<Node> son,int x,int start,int searchTimes){if(can) return;if(x==searchTimes){if(sonUsed.size()==son.size()){can=true;}return;}for(int i=start;i<father.size();i++){Node n = father.get(i);List<Node> sonAdd = new ArrayList<>();for(int j=0;j<n.next.size();j++){Node node = n.next.get(j);if(!sonUsed.contains(node)){sonUsed.add(n.next.get(j));sonAdd.add(node);}}bGraph(father,son,x+1,i+1,searchTimes);for(int j=0;j<sonAdd.size();j++){sonUsed.remove(sonAdd.get(j));}}}public static void main(String args[]) {/*Scanner sc=null;try {sc = new Scanner(new FileInputStream("D://desktop//test.txt"));} catch (FileNotFoundException e) {// TODO Auto-generated catch blocke.printStackTrace();}*/Scanner sc = new Scanner(System.in);String dummy = sc.next();int sender = sc.nextInt();String dummy2 = sc.next();String friend = sc.next();while (!friend.endsWith("End")) {String[] str = friend.split(",");int a = Integer.parseInt(str[0]);int b = Integer.parseInt(str[1]);if (a == b) {friend = sc.next();continue;}Node na;Node nb;if (map.containsKey(a)) {na = map.get(a);} else {na = new Node(a);map.put(a, na);}if (map.containsKey(b)) {nb = map.get(b);} else {nb = new Node(b);map.put(b, nb);}na.next.add(nb);nb.next.add(na);friend = sc.next();}bfs(sender);System.out.println(res-1);sc.close();}}

只有不快的斧，没有劈不开的柴。