リンク

ケビン・ベーコンの6次法則-1389

質問する

ケビン・ベーコンの第6段階の法則によると、地球上の誰もが第6段階でお互いの知っている人に連絡することができる.ケビン・ベーコンゲームは、任意の2人が少なくともいくつかの段階で行うことができるゲームです.
例えば、全く関係ないような仁荷(インハ)大学の李ホホホ氏と西江(ソガン)大学のミン·セヒ氏は、何段階で続けられるだろうか.
千民浩と李浩浩は同じ学校に通っている.千民浩と崔伯俊はBaekjoonオンラインJudgeを通じて知り合った.崔柏俊は金善英とともにスターリングリンクを創設した.金善英と金道は現在、同じ学校のサークルに所属している.金道現と閔世熙は同じ学校に通っていて、知り合いだった.李江浩(イ·ガンホ)、千民浩(チョン·ミンホ)、崔伯俊(チェ·ボジュン)、金善英(キム·ソンヨン)、金道賢(キム·ドヒョン)、閔世煕(ミン·セヒ)のように、5段階だけを経ればいいということだ.
ケビン・ベーコンは、アメリカのハリウッド映画スターたちがケビン・ベーコンゲームを一緒に遊ぶときに現れる段階の総和が最も少ない人だという.
今日BaekjoonオンラインJudgeのプレイヤーの中で、ケビンベーコンの数が一番少ない人を探しています.Kevinベーコンの数は、すべての人とKevinベーコンゲームをしているときに現れる段階の和です.
例えば、BOJのプレイヤーは5名、1と3、1と4、2と3、3と4、4と5が友人であると仮定します.
1は2〜3が2段階、3〜1段階、4〜1段階、5〜4が2段階で分かる.したがって、Kevinベーコンの数は2+1+1+2=6である.
2は、1〜3が2段階、3〜1段階、4〜3が2段階、5〜3及び4が3段階を通過する.したがって、Kevinベーコンの数は2+1+2+3=8である.
3は1から1段階、2から1段階、4から1段階、5から4は2段階しか知らない.したがって、Kevinベーコンの数は1+1+1+2=5である.
4 1から1段階、2から3、2段階、3から1段階、5から1段階でわかります.4のケビンベーコンの数は1+2+1+1=5である.
最後の5は1〜4〜2段階、2〜4及び3は3段階、3〜4は2段階、4〜1段階を通過すれば分かる.5のケビンベーコンの数は2+3+2+1=8です.
5人のプレイヤーの中で、ケビンベーコンの数が最も少ないのは3と4です.
BOJプレイヤーの数と友人関係を入力すると、最も少ないケビンベーコンを探すプログラムを作成してください.

入力

第1行は、ユーザ数N(2≦N≦100)と、親友関係数M(1≦M≦5000)を与える.2行目から、M行には友人関係があります.友人関係はAとBからなり、AとBが友人であることを意味する.AとBが友達なら、BとAも友達で、AとBは同じことはありません.友達関係が繰り返されるかもしれませんが、いない友達は一人もいません.また、誰もが友達の関係でつながっています.人の番号は1からNで、二人は同じ番号を持っていません.

しゅつりょく

1行目の出力BOJプレイヤーの中でケビンベーコンの数が一番小さい人.このような人が複数いれば、出力数が一番小さい人です.

に答える

この問題はフロイドとシエルで解決できる.
今の問題は最小距離数を求めることです.
if(arr[i][j]>arr[i][k]+arr[k][j])ラーメン
arr[i][j]=arr[i][k]+arr[k][j]は、価格の最高値を更新し続けます.では終わります!

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()); //친구명수
		int m=Integer.parseInt(st.nextToken()); //친구사이
		
		int arr[][]=new int[n][n];
		
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
				arr[i][j]=500000;
			
				if(i==j)
					arr[i][j]=0;
			}
		}
		
		for(int i=0; i<m; i++)
		{
			st=new StringTokenizer(br.readLine());
			int num1=Integer.parseInt(st.nextToken())-1;
			int num2=Integer.parseInt(st.nextToken())-1;
			arr[num1][num2]=1;
			arr[num2][num1]=1;
		}
		
		for(int k=0; k<n; k++)
		{
			for(int i=0; i<n; i++)
			{
				for(int j=0; j<n; j++)
				{
					if(arr[i][j] > arr[i][k]+arr[k][j])
						arr[i][j]=arr[i][k]+arr[k][j];
				}
			}
		}
		
		int idx=0;
		int min=Integer.MAX_VALUE;
		
		for(int i=0; i<n; i++)
		{
			int total=0;
			for(int j=0; j<n; j++)
			{
				total+=arr[i][j];
			}
			if(min > total)
			{
				min=total;
				idx=i;
			}
			
		}
		
		System.out.println(idx+1);
	
	}
}