在一个社交应用中,两个用户设定朋友关系后,则可以互相收到对方发布或转发的信息。当一个用户发布或转发一条信息时,他的所有朋友都能收到该信息。
现给定一组用户,及用户之间的朋友关系。
问:当某用户发布一条信息之后,为了让每个人都能在最早时间收到这条信息,这条信息最少需要被转发几次?
假设:对所有用户而言:
1)朋友发出信息到自己收到该信息的时延为T(T>0);
2)如需转发,从收到信息到转发出信息的时延为0。
用例保证:在给定的朋友圈关系中,任何人发布的信息总是能通过N(N>=0)次转发让其他所有用户收到。
例如:
下图表示某个朋友圈关系(节点间连线表示朋友关系)中,用户1在时刻0发布信息之后,两种不同的转发策略。
黄色节点表示转发用户,蓝色数字为用户收到信息的时间。
运行时间限制: | 无限制 |
内存限制: | 无限制 |
输入: |
Sender [消息创建者编号] Relationship [朋友关系列表,1,2 表示1和2是朋友关系] End
如下:
Sender |
输出: |
当某用户发布一条信息之后,为了让每个人都能在最早时间收到这条信息,这条信息最少需要被转发的次数 |
#include <iostream> #include <sstream> #include <vector> #include <queue> #include <map> #include <algorithm> using namespace std; void SetLevelNodeVecMap(map<int,vector<int> >& relation,map<int,vector<int> >& LevelNodeVecMap,int startId) { map<int,int> NodeLevelMap; queue<int> NodeQue; map<int,vector<int> >::iterator it1; vector<int>::iterator it2; NodeLevelMap[startId] = 0; NodeQue.push(startId); while(!NodeQue.empty()) { int nodeId = NodeQue.front(); NodeQue.pop(); it1 = relation.find(nodeId); for(it2 = it1->second.begin(); it2 != it1->second.end(); it2++) { if(NodeLevelMap.find(*it2) == NodeLevelMap.end()) { NodeLevelMap[*it2] = NodeLevelMap[nodeId] + 1; NodeQue.push(*it2); } } } map<int,int>::iterator it; for(it = NodeLevelMap.begin(); it != NodeLevelMap.end(); it++) { LevelNodeVecMap[it->second].push_back(it->first); } } int GetEveryLevelTransmitCounts(map<int,vector<int> >& relation,vector<int> send,vector<int> recv) { int nCount = 0; vector<int>::iterator it1,it2; map<int,int> TrasmitDegrees; // 初始化时就是0 map<int,int>::iterator itD; while(!recv.empty()) { int transmitId = -1; TrasmitDegrees.clear(); for(it1 = recv.begin(); it1 != recv.end(); it1++) { int AdjNum = 0; int lastAdj; vector<int> AdjVec = relation[*it1]; for(it2 = AdjVec.begin(); it2 != AdjVec.end(); it2++) { if(find(send.begin(),send.end(),*it2) != send.end()) { TrasmitDegrees[*it2]++; AdjNum++; lastAdj = *it2; } } if(AdjNum == 1) { transmitId = lastAdj; break; } } if(transmitId == -1) { int maxDegree = 0; for(itD = TrasmitDegrees.begin(); itD != TrasmitDegrees.end(); itD++) { if(itD->second > maxDegree) { maxDegree = itD->second; transmitId = itD->first; } } } nCount++; vector<int> AdjVecToDel = relation[transmitId]; for(it1 = AdjVecToDel.begin(); it1 != AdjVecToDel.end(); it1++) { it2 = find(recv.begin(),recv.end(),*it1); if(it2 != recv.end()) recv.erase(it2); } it1 = find(send.begin(),send.end(),transmitId); send.erase(it1); } return nCount; } int GetTotalTransmitCounts(map<int,vector<int> >& relation,map<int,vector<int> >& LevelNodeVecMap) { int TotalCount = 0; int MaxLevel = LevelNodeVecMap.size() -1; for(int level = 1; level < MaxLevel; level++) { TotalCount = TotalCount + GetEveryLevelTransmitCounts(relation,LevelNodeVecMap[level],LevelNodeVecMap[level+1]); } return TotalCount; } int main(int agrc,char* agrv[]) { string sender,relation; int senderId,a,b; map<int,vector<int> > RelationMap; map<int,vector<int> > LevelNodeVecMap; cin>>sender>>senderId>>relation; while(cin>>relation) { if(relation == "End") break; else { istringstream in(relation); in>>a; in.ignore(); in>>b; RelationMap[a].push_back(b); RelationMap[b].push_back(a); } } SetLevelNodeVecMap(RelationMap,LevelNodeVecMap,senderId); cout<<GetTotalTransmitCounts(RelationMap,LevelNodeVecMap)<<endl; return 0; }