Six Degrees of Cowvin Bacon
Descriptions
数学课上,WNJXYK忽然发现人缘也是可以被量化的,我们用一个人到其他所有人的平均距离来量化计算。
在这里定义人与人的距离:
1.自己与自己的距离为0
2.如果A和B属于同一个小团体,那么他们之间的距离为1
3.如果A与B属于一个小团体,B与C属于一个小团体,且A与C不同属于任何一个小团体,那么A与C的距离为2(A联系C,经过B、C两个人)
4.以此类推
班里有N个人 (2 <= N <= 300),共有M对小团体关系(1 <= M <= 10000)。现在,给你所有班级中小团体的信息,问你班里人缘最好的人到其他人的平均距离。(你需要输出平均距离的100倍)
Input
第一行输入两个证书N,M
接下来的M+1行,每行开头一个整数K表示本小团体大小,然后接下来K个整数表示小团体内学生编号。
Output
输出一行:最小的平均距离*100(程序中请不要使用Float和Double计算,可能会判Wa)
Sample Input
4 2
3 1 2 3
2 3 4
Sample Output
100
题目链接
https://vjudge.net/problem/POJ-2139
最短路问题,把一个团体的人看成相邻的点,之间的距离为1,再用Floyd算法求出每两个人之间的距离即可
Floyd算法详解 https://www.cnblogs.com/sky-stars/p/11204139.html
AC代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 300+5
#define P pair<int,int>
using namespace std;
int n,m,x;
int d[Maxn][Maxn];
void init()
{
//i到j的距离,初始化为无穷大
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
{
if(i==j)//自己
d[i][j]=d[j][i]=;
else
d[i][j]=d[j][i]=INF;
}
}
int main()
{
cin>>n>>m;
init();//初始化
while(m--)
{
cin>>x;
int b[Maxn];//暂时存一下人
for(int i=; i<x; i++)
cin>>b[i];
for(int i=; i<x-; i++)//每两个人之间的距离为1
for(int j=i+; j<x; j++)
d[b[i]][b[j]]=d[b[j]][b[i]]=;
}
//Floyd算法求最短路
for(int k=; k<=n; k++)
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
int ans=INF;
for(int i=; i<=n; i++)//枚举每个人
{
int sum=;
for(int j=; j<=n; j++)
sum+=d[i][j];
ans=min(ans,*sum/(n-));
}
cout<<ans<<endl;
return ;
}