Time Limit : 5000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 36 Accepted Submission(s) : 16

Problem Description

1967年，美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(small world phenomenon)”的著名假说。大意是说。不论什么2个素不相识的人中间最多仅仅隔着6个人。即仅仅用6个人就能够将他们联系在一起。因此他的理论也被称为“六度分离”理论(six degrees of separation)。尽管米尔格兰姆的理论屡屡应验，一直也有非常多社会学家对其兴趣浓厚，可是在30多年的时间里，它从来就没有得到过严谨的证明。仅仅是一种带有传奇色彩的假说而已。

Lele对这个理论相当有兴趣。于是，他在HDU里对N个人展开了调查。

他已经得到了他们之间的相识关系，如今就请你帮他验证一下“六度分离”是否成立吧。

Input

本题目包括多组測试，请处理到文件结束。

对于每组測试，第一行包括两个整数N,M(0<n<100,0<m<200),分别代表hdu里的人数（这些人分别编成0~n-1号)，以及他们之间的关系。 <="" div="" 除了这m组关系。其它随意两人之间均不相识。="" 接下来有m行，每行两个整数a,b(0<="A,B<N)表示HDU里编号为A和编号B的人互相认识。

Output

对于每组測试。假设数据符合“六度分离”理论就在一行里输出"Yes"，否则输出"No"。

Sample Input

Sample Output

Yes

Yes

#include<stdio.h>

#include<string.h>

#define M  10000000

#define min(a,b) (a)>(b)?(b):(a)

int map[202][202];

int vis[202],dist[202];

int n,s,t,flag;

int  dijkstra(int s)

{

    int min,i,j,k;

    memset(vis,0,sizeof(vis));

    for(i=0; i<n; i++)

        dist[i]=M;

    dist[s]=0;

    for(i=0; i<n; i++)

    {

       k=-1;

        for(j=0; j<n; j++)

            if(!vis[j]&&(k==-1||dist[j]<dist[k]))

                k=j;

        if(dist[k]>7||k==-1)

		{

			flag=0;

			return 0;

		}

        vis[k]=1;

        for(j=0; j<n; j++)

        dist[j]=min(dist[j],dist[k]+map[k][j]);

    }

   return 1;

}

int main()

{

    int i,j,x,y,z,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

    	flag=1;

        for(i=0; i<n; i++)

            for(j=0; j<n; j++)

                map[i][j]=map[j][i]=M;

        for(i=0; i<m; i++)

        {

            scanf("%d%d",&x,&y);

                map[y][x]=1;

                map[x][y]=1;

        }

        for(i=0;i<n;i++)

        if(!dijkstra(i))//少了一个！

break;

        if(flag)

        printf("Yes\n");

        else printf("No\n");

    }

    return 0;

}

再贴一个spfa算法写的代码。

#include<stdio.h>

#include<queue>

#include<string.h>

#include<algorithm>

using namespace std;

struct stu{

    int one,two,val,next;

};

stu edge[30000];

int vid[3000],vist[30000],head[30000],t,N,M,flag;

int spfa(int s)

{

    memset(vid,0,sizeof(vid));

    memset(vist,0x3f3f3f3f,sizeof(vist));

    queue<int> q;

    q.push(s);

    vid[s]=1;

    vist[s]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vid[u]=0;

        for(int i=head[u];i!=-1;i=edge[i].next)

        {

            int v=edge[i].two;

            if(vist[v]>vist[u]+edge[i].val)

            {

                vist[v]=vist[u]+edge[i].val;

                if(!vid[v])

                {

                    q.push(v);

                    vid[v]=1;

                }

            }

        }

    }

    for(int i=0;i<N;++i)

        if(vist[i]>7)

        {

            flag=0;

            return 0;

        }

    return 1;

}

void get(int u,int v,int w)

{

    stu E={u,v,w,head[u]};

    edge[t]=E;

    head[u]=t++;

}

int main()

{

    while(scanf("%d%d",&N,&M)!=EOF)

    {

        t=0;

        flag=1;

        memset(head,-1,sizeof(head));

        int i,j,a,b,c;

        for(i=0;i<M;i++)

        {

            scanf("%d%d",&a,&b);

            get(a,b,1);

            get(b,a,1);

        }

        for(i=0;i<N;i++)

        if(!spfa(i))

        break;

        if(flag)

        printf("Yes\n");

        else printf("No\n");

    }

    return 0;

}

再贴一个floyd（）算法写的程序

#include<stdio.h>

#include<string.h>

#define INL 0x3f3f3f3f

#define min(a,b)  (a)>(b)?(b):(a)//这个地方弄错了，弄成大于了。把这个改了一下就不超时了

int x[110][110];

int n,m;

void floyd()

{

	for(int k=0;k<n;k++)

	    for(int i=0;i<n;i++)

	       for(int j=0;j<n;j++)

	       x[i][j]=min(x[i][j],x[i][k]+x[k][j]);

}

int main()

{

	int i,j,k,flag,a,b;

	while(scanf("%d%d",&n,&m)!=EOF)

	{

		for(i=0;i<n;i++)//这个地方应该写成n，错写成m了<img alt="哭" src="http://static.blog.csdn.net/xheditor/xheditor_emot/default/cry.gif" />

				for(j=0;j<m;j++)

						x[i][j]=INL;

		for(i=0;i<m;i++)

		{

			scanf("%d%d",&a,&b);

		   x[a][b]=x[b][a]=1;

		}

	    floyd();

             flag=0;

	    for(i=0;i<n;i++)

	    {

	    	for(j=0;j<n;j++)

			    if(x[i][j]>7||x[i][j]==INL)

			    {

			    	flag=1;

			    	break;

			    }

			    if(flag)

			    break;

	    }

	    if(flag)

	    printf("No\n");

	    else  printf("Yes\n");

	}

	return 0;

}

巴特西

六度分离（floyd算法,SPFA算法,最短路—Dijkstra算法）

Time Limit : 5000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 36 Accepted Submission(s) : 16

最新文章

热门文章