六度空间

“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。“六度空间”理论虽然得到广泛的认同,并且正在得到越来越多的应用。但是数十年来,试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因,这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具,能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。假如给你一个社交网络图,请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式

输入第1行给出两个正整数,分别表示社交网络图的结点数NN1<N1031<N≤10^3,表示人数)、边数MM33×N≤33×N,表示社交关系数)。随后的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;
}