Six Degrees of Cowvin Bacon(最短絡)
The cows have been making movies lately,so they are ready to Play a variant of the famous game"Six Degrees of Kevin Bacon" The game works like this:each cow is consided to be zerdegrees of separation away from heself.If twork distinct cows been a movie together,each is considedededededededededededededededers to be'away frem therever.If.ews.they are consideed to be two'degrees'away from each other(counted as:one degree to the cow the cow the've workd with and one more to the other cow)This scales to the general case.
The N(2==N==300)cows are interested in figring out which cow has the smareet degree of separation from all the other cows.excluding hers herelf of course.The cows have made M(1=M=gures moversis)
Input*Line 1:Two space-separated integers:N and M * Lines 2.M＋1:Each input line contains a set of two or more space-separated integers that describes the cows the cows apering in a single movie.The first integer is the number of cows particining the demorise.morise.the subsequent Mi integers tell which cows were. Output
*Line 1:A single integer that is 100 times the shotest mean degree of separation of any of the cows.
Sample Input 4 2 3 1 2 3 3 3 4 Sample Output
100
ベント
[Cow 3 has workd with all the other cows and thus has degrees of separation:1,and 1--a mean of 1.00.]
考え方:最も短絡的な問題.
図を建てる時、対角線を一列に0に設定し、残りは初期状態でINF無限大に設定します.
そして、1セットの要素間の距離を1に設定します.(ここの図は対称行列です!!)
その後、間接的に関係する座標Map[i]=min(Map[i]、[j],Map[i]+Map[k]+Map[j])をFloydアルゴリズムで更新する.
最後にMin＊100/(n-1)を出力します.(ここでは100を先に乗って平均を取ります.intの数が整除できないと小数点以下の数を切り捨てます.結果は100倍に拡大して誤差が大きいです.!)
The N(2==N==300)cows are interested in figring out which cow has the smareet degree of separation from all the other cows.excluding hers herelf of course.The cows have made M(1=M=gures moversis)
Input*Line 1:Two space-separated integers:N and M * Lines 2.M＋1:Each input line contains a set of two or more space-separated integers that describes the cows the cows apering in a single movie.The first integer is the number of cows particining the demorise.morise.the subsequent Mi integers tell which cows were. Output
*Line 1:A single integer that is 100 times the shotest mean degree of separation of any of the cows.
Sample Input 4 2 3 1 2 3 3 3 4 Sample Output
100
ベント
[Cow 3 has workd with all the other cows and thus has degrees of separation:1,and 1--a mean of 1.00.]
考え方:最も短絡的な問題.
図を建てる時、対角線を一列に0に設定し、残りは初期状態でINF無限大に設定します.
そして、1セットの要素間の距離を1に設定します.(ここの図は対称行列です!!)
その後、間接的に関係する座標Map[i]=min(Map[i]、[j],Map[i]+Map[k]+Map[j])をFloydアルゴリズムで更新する.
最後にMin＊100/(n-1)を出力します.(ここでは100を先に乗って平均を取ります.intの数が整除できないと小数点以下の数を切り捨てます.結果は100倍に拡大して誤差が大きいです.!)
#include
#include
#include
#define INF 99999999
using namespace std;
int main()
{
int n,m,t,a[305];
int Map[305][305];
scanf("%d %d",&n,&m);
for(int i=0;i<=n;i++)
{
Map[i][i]=0;
for(int j=i+1;j<=n;j++)
Map[i][j]=Map[j][i]=INF;
}
for(int i=1;i<=m;i++)
{
scanf("%d",&t);
for(int j=1;j<=t;j++)
scanf("%d",&a[j]);
for(int x=1;x<=t;x++)
for(int y=x+1;y<=t;y++)
Map[a[x]][a[y]]=Map[a[y]][a[x]]=1;
}
for(int k=1;k<=n;k++)//Floyd
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
Map[i][j]=min(Map[i][j],
Map[i][k]+Map[k][j]);
}
}
}
/*for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
printf("%10d",Map[i][j]);
printf("
");
}*/
int Min=INF,temp;
for(int i=1;i<=n;i++)
{
temp=0;
for(int j=1;j<=n;j++)
temp+=Map[i][j];
if(temp