计蒜客习题：蒜厂年会

---

问题描述

蒜厂要开年会了，所有的员工都要参加。
每两个员工之间都有一个亲密度。在同一个项目工作过的员工之间的亲密度为 1。如果 A 和 B、B 和 C 均在同一个项目中工作过，而 A 和 C 没有，那么 A 和 C 之间的亲密度为 1+1=2。
同理，如果 A 和 B 之间的亲密度为 x，B 和 C 之间的亲密度为 y，则 A 和 C 之间的一种 可能亲密度 为 x+y。两个人之间的 亲密度 为所有的 可能亲密度 之中的 最小值。
因为蒜厂里员工之间非常有爱，所以保证每两个员工之间都可以算出一个亲密度。
现在有一个名单，已知蒜厂在这一年一共进行过 M 个项目，N 名员工都想知道自己与其他所有员工的亲密度的平均值，现在你需要找出所有员工中，与其他所有员工 亲密度平均值 最小的员工，即和其他所有员工最亲密的一名员工，来担任这次年会的主持人。
输入格式
一行两个整数 N 和 M，(1≤M≤10000,2≤N≤300)。
接下来 M 行，表示 M 个项目名单,每行第一个整数表示参加这一个项目的员工人数，后面是这些员工的编号，所有员工的编号从 1 开始计数。
输出格式
一行一个整数，为最小的亲密度平均值乘 100 以后向下取整。
样例输入
4 2
3 1 2 3
2 3 4
样例输出
100

---

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int G[320][320];
int INF = 0x3f3f3f3f;
int buf1[320];
int buf2[320];
int main() {
memset(G,INF, sizeof(G));
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int t;
cin >> t;
for (int j = 0; j < t; j++) {
cin >> buf1[j];
      buf2[j] = buf1[j];
    }
for (int x = 0; x < t; x++) {
for (int y = 0; y < t; y++) {
if(x!=y)G[buf1[x]][buf2[y]] = 1;
      }
    }
  }
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if ((i!=j)&&(G[i][j] > G[i][k] + G[k][j]))
          G[i][j] = G[i][k] + G[k][j];
      }
    }
  }
double MINV=INF;
for (int i= 1; i<= n; i++) {
double sumn = 0;
for (int j = 1; j<= n; j++) {
if(i!=j)sumn += G[i][j];
    }
    MINV = min(sumn/(n-1), MINV);
  }
cout << (int)(MINV * 100);
return 0;
}