题目链接
Six Degrees of Cowvin Bacon POJ - 2139
思路
$$ Floyd-Warshall算法模板题,注意输出格式sum * 100 / (n - 1) $$
时间复杂度
$$ O(N^3) $$
代码
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
class Floyd {
public:
typedef long long T;
vector<vector<T> > dist;
int n;
void init(int _n) {
n = _n;
vector<T> temp(n + 5);
dist.resize(n + 5, temp);
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dist[i][j] = INF;
if (i == j) {
dist[i][j] = 0;
}
}
}
}
void add_edge(int u, int v, T w) {
dist[u][v] = min(dist[u][v], w);
}
void add_edges(int u, int v, T w) {
add_edge(u, v, w);
add_edge(v, u, w);
}
void gao() {
for (int k = 0; k <= n; k++) {
for (int i = 0; i <= n; i++) {
for (int j = 0;j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
};
int main() {
Floyd floyd;
int n, m;
scanf("%d%d", &n, &m);// don't forget &
floyd.init(n);
while (m--) {
int k;
scanf("%d", &k);// don't forget &
vector<int> a(k);
for (int i = 0; i < k; i++) {
scanf("%d", &a[i]);// don't forget &
for (int j = 0; j < i; j++) {
floyd.add_edges(a[j], a[i], 1);
}
}
}
floyd.gao();
long long ans = INF;
for (int i = 1; i <= n; i++) {
long long cur = 0;
for (int j = 1; j <= n; j++) {
cur += floyd.dist[i][j];
}
ans = min(ans, cur);
}
printf("%lld", ans * 100 / (n - 1));
return 0;
}