继续更新一道基础题
题：朋友圈转发信息描述 ：在一个社交应用中，两个用户设定朋友关系后，则可以互相收到对方发布或转发的信息。当一个用户发布或转发一条信息时，他的所有朋友都能收到该信息。 现给定一组用户，及用户之间的朋友关系。问：当某用户发布一条信息之后，为了让每个人都能在最早时间收到这条信息，这条信息最少需要被转发几次？ 假设：对所有用户而言：1）朋友发出信息到自己收到该信息的时延为T（T>0）；2）如需转发，从收到信息到转发出信息的时延为0。 用例保证：在给定的朋友圈关系中，任何人发布的信息总是能通过N（N>=0）次转发让其他所有用户收到。 例如：下图表示某个朋友圈关系（节点间连线表示朋友关系）中，用户1在时刻0发布信息之后，两种不同的转发策略。黄色节点表示转发用户，蓝色数字为用户收到信息的时间
样例输入：
Sender
1
Relationship
1,21,31,42,52,63,64,64,75,65,85,96,76,86,97,910,7End
输出（当某用户发布一条信息之后，为了让每个人都能在最早时间收到这条信息，这条信息最少需要被转发的次数）：
4
解决代码：
#include <iostream>
#include <utility>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define NoLevel -1
typedef pair<int,int> RELATIONSHIP; //获取输入的一行关系
typedef pair<int,int> FORWARDINFO;
bool pairSort(const FORWARDINFO &e1,const FORWARDINFO &e2)
{
return e1.second<e2.second;
}
struct node
{
int id;
vector<int> id_friend;
int IsKnow;
bool IsForward;
int relativeLevel;
node(int pid,vector<int> pid_friend,int pIsKnow,bool pIsForword)
{
this->id=pid;
this->IsKnow=pIsKnow;
this->IsForward=pIsForword;
this->id_friend=pid_friend;
this->relativeLevel=NoLevel;
}
};
class UDGraph
{
private:
int vetexcount;
int MaxLevel;
vector<node> vetex;
vector<int> GetFriendId(vector<RELATIONSHIP> relationship,int id)
{
vector<int> unit;
vector<RELATIONSHIP>::iterator it;
for(it=relationship.begin();it!=relationship.end();++it)
{
//cout << it->first << "\t" << it->second << endl;
if(it->first==id)
{
unit.push_back(it->second);
}
if(it->second==id)
{
unit.push_back(it->first);
}
}
return unit;
}
int unforward(FORWARDINFO forwardinfo)
{
int id=forwardinfo.first;
vector<int>::iterator itfriend;
for(itfriend=(vetex.id_friend).begin();itfriend!=(vetex.id_friend).end();++itfriend)
{
if((vetex[*itfriend-1].relativeLevel)>(vetex.relativeLevel))
{
int temp=(vetex[*itfriend-1].IsKnow)-1;
if(temp<=0)
{
return 0;
}
}
}
for(itfriend=(vetex.id_friend).begin();itfriend!=(vetex.id_friend).end();++itfriend)
{
if((vetex[*itfriend-1].relativeLevel)>(vetex.relativeLevel))
{
--(vetex[*itfriend-1].IsKnow);
}
}
return 1;
}
int forward(int id)
{
int count=0;
vector<int>::iterator itfriend;
for(itfriend=(vetex.id_friend).begin();itfriend!=(vetex.id_friend).end();++itfriend)
{
if((vetex[*itfriend-1].relativeLevel)>(vetex.relativeLevel))
{
++(vetex[*itfriend-1].IsKnow);
++count;
}
}
return count;
}
int GetEachLevelNum(vector<int> levelData)
{
int result=0;
vector<FORWARDINFO> forwardInfo;
vector<int>::iterator itdata;
for(itdata=levelData.begin();itdata!=levelData.end();++itdata)
{
forwardInfo.push_back(make_pair(*itdata,forward(*itdata)));
}
sort(forwardInfo.begin(),forwardInfo.end(),pairSort);
int deleteNum=0;
vector<FORWARDINFO>::iterator itforward;
for(itforward=forwardInfo.begin();itforward!=forwardInfo.end();++itforward)
{
if(unforward(*itforward)==1)
{
++deleteNum;
}
}
if(forwardInfo.size())
{
//cout << forwardInfo.size() << endl;
result=forwardInfo.size()-deleteNum;
}
return result;
}
void SetRelativeLevel(int sender,int startLevel) //有待优化
{
if(MaxLevel<startLevel)
{
MaxLevel=startLevel;
}
vector<int>::iterator itfriend;
vetex.relativeLevel=startLevel;
for(itfriend=(vetex.id_friend).begin();itfriend!=(vetex.id_friend).end();++itfriend)
{
if(vetex[*itfriend-1].relativeLevel==NoLevel)
{
SetRelativeLevel(*itfriend,startLevel+1);
}
else if(vetex[*itfriend-1].relativeLevel>(startLevel+1))
{
SetRelativeLevel(*itfriend,startLevel+1);
}
}
}
public:
UDGraph(vector<RELATIONSHIP> relationship,int count)
{
this->vetexcount=count;
for(int index=0;index<count;++index)
{
vector<int> friendid=GetFriendId(relationship,index+1);
vetex.push_back(node(index+1,friendid,0,false));
}
MaxLevel=0;
}
int GetLeastStep(int sender)
{
int result=0;
SetRelativeLevel(sender,1);
//cout << MaxLevel << endl;
vector<int> LevelData;
for(int level=2;level<=MaxLevel;++level)
{
vector<node>::iterator itnode;
for(itnode=vetex.begin();itnode!=vetex.end();++itnode)
{
if(itnode->relativeLevel==level)
{
LevelData.push_back(itnode->id);
}
}
}
/*
for(int level=2;level<MaxLevel;++level)
{
cout << endl;
vector<int>::iterator it;
for(it=LevelData.begin();it!=LevelData.end();++it)
{
cout << *it << "";
}
cout << endl;
}*/
for(int level=MaxLevel;level>2;--level)
{
result+=GetEachLevelNum(LevelData);
}
return result;
}
void display()
{
cout << endl;
vector<node>::iterator itnode;
for(itnode=vetex.begin();itnode!=vetex.end();++itnode)
{
cout << "id:\t" << itnode->id << endl;
cout << "IsKnow:\t" << itnode->IsKnow << endl;
cout << "IsForward:\t" << itnode->IsForward << endl;
cout << "relativeLevel:\t" << itnode->relativeLevel << endl;
cout << "id_friend:\t";
vector<int>::iterator itid;
for(itid=(itnode->id_friend).begin();itid!=(itnode->id_friend).end();++itid)
{
cout << *itid << "\t";
}
cout << endl;
cout << endl;
}
}
};
void GetInput(int *sender,vector<RELATIONSHIP> *relationship)
{
string input;
getline(cin,input);
if(input=="Sender")
{
cin >> *sender;
fflush(stdin);
getline(cin,input);
if(input=="Relationship")
{
while(true)
{
fflush(stdin);
getline(cin,input);
if(input=="End")
{
break;
}
else
{
int pos=input.find(",",0);
RELATIONSHIP relationship_pair=make_pair(atoi(input.substr(0,pos).c_str()),atoi(input.substr(pos+1,input.length()).c_str()));
relationship->push_back(relationship_pair);
}
}
}
}
}
int main()
{
int sender=-1;
vector<RELATIONSHIP> Relationship;
GetInput(&sender,&Relationship);
/*
cout << sender << endl;
vector<RELATIONSHIP>::iterator it;
for(it=Relationship.begin();it!=Relationship.end();++it)
{
cout << it->first << "\t" << it->second << endl;
}*/
UDGraph *graph=new UDGraph(Relationship,10);
int least=graph->GetLeastStep(sender);
//graph->display();
cout << least;
return 0;
}
主要思想：
1，先把每个元素分级（级数=距离始发者最短距离，发送者为0级）
2，从倒数第二级开始：
a:将该级所有元素假设为转发状态，并将其上一级的所有朋友的知道状态（IsKnow）加1.
b:根据上一级的朋友数量排序。从小到大做假定删除检验,如果删除了，其上一级朋友的知道状态依然大于0，则可删除,并对朋友知道状态减1.
c:得到该级必须要转载的人的数目=该级总人数-可删除（并已删除）人数。
d:级数减1.
总结:
感觉真正上机考试时间不够，代码是第一版本，没优化。
学习一下 这是树？ Android_army 发表于 2016-9-10 16:23
这是树？
这应该是无向图，但是由于数据结构没学好，就用这种不正规的方式解决了 好厉害 赞一个 {:301_996:} 我也看看。路过。哈哈。 天书啊！看不懂，这个用到？没学过 以前学习过一段时间，看了这么长的代码为楼主的付出赞一个 Android_army 发表于 2016-9-10 16:23
这是树？
dp。。。。 从最下面开始找，可以看似是dp的思路。。。但是如果从上向下dfs效率也可以，但是因为记忆化搜索容易爆栈、、、
页:
[1]
2