HDoj 1869六度分離【最短経路で両辺の間の最長辺を求める】
2873 ワード
ろくどぶんり
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5443 Accepted Submission(s): 2208
Problem Description
1967年、米国の著名な社会学者スタンリー・ミルグランムは「小世界現象(small world phenomenon)」という有名な仮説を提出した.(six degrees of separation).ミルグラムの理論はしばしば当てはまり、多くの社会学者が興味を持っていたが、30年以上も厳密な証明を得たことがなく、伝奇的な仮説にすぎなかった.
Leleはこの理論にかなり興味を持っていたので、HDUでN人に対して調査を行いました.彼はすでに彼らの間の知り合い関係を得ています.今、「六度分離」が成立したかどうかを検証してください.
Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.
各試験群について、第1行は2つの整数N,M(0次にM行があり、行ごとに2つの整数A、B(0<=A、BこのM組の関係を除いて、他の2人は知り合いではありません.
Output
各グループのテストについて、データが「6度分離」理論に合致する場合は、1行に「Yes」を出力し、そうでない場合は「No」を出力します.
Sample Input
8 7
0 1
1 2
2 3
3 4
4 5
5 6
6 7
8 8
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0
Sample Output
Yes
Yes
标题:任意の2人の間を最大6人で結ぶことを六度分離という
考え方:任意の2人の間の最短ルートを7未満にすればよい
dijkstraアルゴリズム:
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5443 Accepted Submission(s): 2208
Problem Description
1967年、米国の著名な社会学者スタンリー・ミルグランムは「小世界現象(small world phenomenon)」という有名な仮説を提出した.(six degrees of separation).ミルグラムの理論はしばしば当てはまり、多くの社会学者が興味を持っていたが、30年以上も厳密な証明を得たことがなく、伝奇的な仮説にすぎなかった.
Leleはこの理論にかなり興味を持っていたので、HDUでN人に対して調査を行いました.彼はすでに彼らの間の知り合い関係を得ています.今、「六度分離」が成立したかどうかを検証してください.
Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.
各試験群について、第1行は2つの整数N,M(0
Output
各グループのテストについて、データが「6度分離」理論に合致する場合は、1行に「Yes」を出力し、そうでない場合は「No」を出力します.
Sample Input
8 7
0 1
1 2
2 3
3 4
4 5
5 6
6 7
8 8
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0
Sample Output
Yes
Yes
标题:任意の2人の間を最大6人で結ぶことを六度分離という
考え方:任意の2人の間の最短ルートを7未満にすればよい
dijkstraアルゴリズム:
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define INF 0x3f3f3f
int map[MAX][MAX],vis[MAX];
int low[MAX];
int n,m;
int ok;
void prime(int y,int x)
{
int i,j,next;
int min,mincost=0;
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
{
low[i]=map[y][i];
}
vis[y]=1;
for(i=0;i<n-1;i++)
{
min=INF;
for(j=0;j<n;j++)
{
if(!vis[j]&&min>low[j])
{
min=low[j];
next=j;
}
}
vis[next]=1;
for(j=0;j<n;j++)
{
if(!vis[j]&&low[j]>map[next][j]+low[next])
low[j]=map[next][j]+low[next];
}
}
if(low[x]==INF||low[x]-1>6)
{
ok=0;
printf("No
");
}
}
int main()
{
int j,i,s,t,l;
int a,b;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
map[i][j]=map[j][i]=0;
else
map[i][j]=INF;
}
}
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
map[a][b]=map[b][a]=1;
}
ok=1;
for(j=0;j<n;j++)
{
for(i=0;i<n;i++)
{
prime(j,i);
if(ok==0)
break;
}
if(ok==0)
break;
}
if(ok)
printf("Yes
");
}
return 0;
}