【POJ - 2139】Six Degrees of Cowvin Bacon （Floyd算法求最短路）

佚名 5年前 (2019-08-13) 算法 1496人围观抢沙发百度已收录

Six Degrees of Cowvin Bacon

Descriptions

数学课上，WNJXYK忽然发现人缘也是可以被量化的，我们用一个人到其他所有人的平均距离来量化计算。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

在这里定义人与人的距离：
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>1
#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=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            if(i==j)//自己
                d[i][j]=d[j][i]=0;
            else
                d[i][j]=d[j][i]=INF;
        }
}
int main()
{
    cin>>n>>m;
    init();//初始化
    while(m--)
    {
        cin>>x;
        int b[Maxn];//暂时存一下人
        for(int i=0; i<x; i++)
            cin>>b[i];
        for(int i=0; i<x-1; i++)//每两个人之间的距离为1
            for(int j=i+1; j<x; j++)
                d[b[i]][b[j]]=d[b[j]][b[i]]=1;
    }
    //Floyd算法求最短路
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    int ans=INF;
    for(int i=1; i<=n; i++)//枚举每个人
    {
        int sum=0;
        for(int j=1; j<=n; j++)
            sum+=d[i][j];
        ans=min(ans,100*sum/(n-1));
    }
    cout<<ans<<endl;
    return 0;
}