5.六度空间、哈利波特的考试
六度空间
“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式
输入第1行给出两个正整数,分别表示社交网络图的结点数(,表示人数)、边数(,表示社交关系数)。随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个结点的编号(节点从1到N编号)。
输出格式
对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比,精确到小数点后2位。
每个结节点输出一行,格式为“结点编号:(空格)百分比%”。
输入样例
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
输出样例
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%
算法思路
- 对每个结点,进行广度优先搜索
- 搜索过程中累计访问的结点数
- 需要记录层数,仅计算6层以内的结点数
void SDS()
{
for(each V in G)
{
count=BFS(V);
Output(count/N);
}
}
int BFS(Vertex V)
{
visited[V]=true;
count=1,level=0,last=V;
Enqueue(V,Q);
while(!IsEmpty(Q))
{
V=Dequeue(Q);
for(V的每个邻接点W)
if(!visited[W])
{
visited[W]=true;
Enqueue(W,Q);
count++;
tail=W;
}
if(V==last)
{
level++;
last=tail;
}
if(level==6)break;
}
return count;
}
ac代码
#include<iostream>
#include<queue>
#define MaxPeople 1000
#define MaxSocial 33
using namespace std;
typedef int Vertex;
typedef struct ENode *PtrToENode;
typedef struct AdjVNode *PtrToAdjVNode;
typedef struct LGNode *PtrToLGNode;
typedef struct Vnode AdjList[MaxPeople];
typedef PtrToENode Edge;
typedef PtrToLGNode LGraph;
struct ENode{
Vertex V1, V2;
};
struct AdjVNode{
Vertex AdjV;
PtrToAdjVNode Next;
};
struct Vnode{
PtrToAdjVNode FirstEdge;
};
struct LGNode{
int Nv,Ne;
AdjList G;
};
LGraph CreateLGraph(int);
void InsertLGraph(Edge,LGraph);
void BuildLGraph(LGraph,int);
void SDS(LGraph,bool*);
int BFS(LGraph,Vertex,bool*);
int main(int argc,char*argv[]) {
int n,m;
cin>>n>>m;
bool visited[n+1];
LGraph L= CreateLGraph(n);
BuildLGraph(L,m);
SDS(L,visited);
}
LGraph CreateLGraph(int VertexNum){
auto L=new struct LGNode;
L->Nv=VertexNum,L->Ne=0;
for(int i=0;i `<L->`Nv;i++)L->G[i].FirstEdge= nullptr;
return L;
}
void InsertLGraph(Edge E,LGraph L){
PtrToAdjVNode newnode1,newnode2;
newnode1=new struct AdjVNode;
newnode2=new struct AdjVNode;
newnode1->AdjV=E->V2;
newnode2->AdjV=E->V1;
newnode1->Next=L->G[E->V1-1].FirstEdge;
newnode2->Next=L->G[E->V2-1].FirstEdge;
L->G[E->V1-1].FirstEdge=newnode1;
L->G[E->V2-1].FirstEdge=newnode2;
L->Ne++;
}
void BuildLGraph(LGraph L,int m){
for(int i=0;i<m;i++){
auto E=new struct ENode;
cin>>E->V1>>E->V2;
InsertLGraph(E,L);
}
}
void SDS(LGraph L,bool* visited){
float count;
for(int i =1;i<=L->Nv;i++){
for(int j=1;j<=L->Nv;j++)visited[j]= false;
count=(float)BFS(L,i,visited);
printf("%d: %.2f%%\n",i,100*count/(float)L->Nv);
}
}
int BFS(LGraph L,Vertex V,bool* visited){
queue `<Vertex>` q;
int count=1,level=0;
Vertex last=V,tail;
PtrToAdjVNode W;
visited[V]=true;
q.push(V);
while(!q.empty()){
V=q.front(),q.pop();
W = L->G[V-1].FirstEdge;
while(W){
if(!visited[W->AdjV]){
q.push(W->AdjV);
visited[W->AdjV]= true,tail=W->AdjV,count++;
}
W=W->Next;
}
if(V==last)last=tail,level++;
if(level==6)break;
}
return count;
}
哈利·波特的考试
哈利·波特要考试了,他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha,将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念,例如ahah可以将老鼠变成猫。另外,如果想把猫变成鱼,可以通过念一个直接魔咒lalala,也可以将猫变老鼠、老鼠变鱼的魔咒连起来念:hahahehe。现在哈利·波特的手里有一本教材,里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场,要考察他把这只动物变成任意一只指定动物的本事。于是他来问你:带什么动物去可以让最难变的那种动物(即该动物变为哈利·波特自己带去的动物所需要的魔咒最长)需要的魔咒最短?例如:如果只有猫、鼠、鱼,则显然哈利·波特应该带鼠去,因为鼠变成另外两种动物都只需要念4个字符;
而如果带猫去,则至少需要念6个字符才能把猫变成鱼;同理,带鱼去也不是最好的选择。
输入格式
输入说明:输入第1行给出两个正整数N(≤100)和M,其中N是考试涉及的动物总数,M是用于直接变形的魔咒条数。为简单起见,我们将动物按1~N编号。随后M行,每行给出了3个正整数,分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100),数字之间用空格分隔。
输出格式
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度,中间以空格分隔。
如果只带1只动物是不可能完成所有变形要求的,则输出0。如果有若干只动物都可以备选,则输出编号最小的那只。
输入样例
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
输出样例
4 70
程序框架搭建
题意理解:任意两顶点间的最短路径-Floyd算法
int main()
{
MGraph G=BuildGraph();
FindAnimal(G);
}
MGraph的定义:CreateGraph,InsertEdge——>BuildGraph
Floyd算法:FindMaxDist(i)——>FindMin——>FindAnimal
选择动物
void FindAnimal(MGraph Graph)
{
WeightType D[MaxVertex][MaxVertex],MaxDist,MinDist;
Vertex Animal,i;
Floyd(Graph,D);
MinDist=INFINITY;
for(i=0;i<Graph->Nv;i++)
{
MaxDist=FindMaxDist(D,i,Graph->Nv);
if(MaxDist==INFINITY)
{
cout<<0<<endl;
return;
}
if(MinDist>MaxDist)
{
MinDist=MaxDist;
Animal=i+1;
}
}
cout<<Animal<<' '<<MinDist<<endl;
}
WeightType FindMaxDist(WeightType D[][MaxVertexNum],Vertex i,int N)
{
WeightType MaxDist;
Vertex j;
MaxDist=0;
for(j=0;j<N;j++)
if(i!=j&&D[i][j]>MaxDist)MaxDist=D[i][j];
return MaxDist;
}
ac代码
#include<iostream>
#define MaxAnimal 101
#define INFINITY 65535
using namespace std;
void BuildGragh(int,int);
void Floyd(int);
int MGraph[MaxAnimal][MaxAnimal],D[MaxAnimal][MaxAnimal];
int main(){
int n,m;
cin>>n>>m;
BuildGragh(n,m);
Floyd(n);
}
void BuildGragh(int n,int m){
int v,w,weight;
for(int i=0;i<MaxAnimal;i++)for(int j=0;j<MaxAnimal;j++)
if(i!=j)MGraph[i][j]=INFINITY;
for(int i=0;i<m;i++){
cin>>v>>w>>weight;
MGraph[v][w]=MGraph[w][v]=weight;
}
}
void Floyd(int n){
int dist[MaxAnimal+1]={0},minp=INFINITY,mini;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
D[i][j]=MGraph[i][j];
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
if(D[i][j]>D[i][k]+D[k][j])D[i][j]=D[i][k]+D[k][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)if(D[i][j]>dist[i])dist[i]=D[i][j];
if(minp>dist[i])minp=dist[i],mini=i;
}
if(minp<INFINITY)cout<<mini<<' '<<minp<<endl;
else cout<<0<<endl;
}