POJ 2139 Six Degrees of Cowvin Bacon （Floyd）

题意：如果两头牛在同一部电影中出现过，那么这两头牛的度就为1， 如果这两头牛a，b没有在同一部电影中出现过，但a，b分别与c在同一部电影中出现过，那么a，b的度为2。以此类推，a与b之间有n头媒介牛，那么a，b的度为n+1。 给出m部电影，每一部给出牛的个数，和牛的编号。问那一头到其他每头牛的度数平均值最小，输出最小平均值乘100

思路：到所有牛的度数的平均值最小，也就是到所有牛的度数总和最小。那么就是找这头牛到其他每头牛的最小度，也就是最短路径，相加再除以（n-1）就是最小平均值。对于如何确定这头牛，我们可以用Floyd枚举，最后记录最下平均值即可。

#include<iostream>

#include <algorithm>

using namespace std;

const int MAXN = 301;

const int INF = 99999;

int d[MAXN][MAXN], dis[MAXN], N, M;

void solve()

{

	int ans = INF;

	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]);

			}

		}

	}

	for (int i = 1; i <= N; i++){

		for (int j = 1; j <= N; j++){

			d[i][0] += d[i][j];

		}

		d[i][0] = 100 * d[i][0] / (N - 1);

		ans = min(ans, d[i][0]);

	}

	cout << ans << endl;

}

int main()

{

	while (cin >> N >> M)

	{

		for (int i = 1; i <= N; i++)

		for (int j = 1; j <= N; j++){

			d[i][j] = INF;

			if (i == j) d[i][j] = 0;

		}

		for (int i = 1; i <= M; i++){

			int num;

			cin >> num;

			for (int i = 1; i <= num; i++) cin >> dis[i];

			for (int i = 1; i <= num; i++){

				for (int j = i + 1; j <= num; j++){

					d[dis[i]][dis[j]] = 1;

					d[dis[j]][dis[i]] = 1;

				}

			}

		}

		solve();

	}

	return 0;

}