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


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>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;
}

 


作者:Sky丨Star,发布于:2019/08/13
原文:https://www.cnblogs.com/sky-stars/p/11346995.html