|
|
也可以用floyd。
 #include <stdio.h>
#include <string.h>
#define MAX_N 332
char conn[MAX_N][MAX_N], visited[MAX_N];
int N, M, qh, qt, min_val, val;
  struct  {
 int step, idx;
 } queue[MAX_N];
__inline void insert(int i, int s)
{
if (visited[i])
return ;
queue[qt].idx = i;
queue[qt].step = s;
val += s;
qt++;
visited[i] = 1;
}
__inline void bfs(int idx)
{
int i, step;
memset(visited, 0, N + 1);
val = qh = qt = 0;
insert(idx, 0);
  while (qh != qt) {
idx = queue[qh].idx;
step = queue[qh].step;
qh++;
for (i = 1; i <= N; i++)
if (conn[idx][i])
insert(i, step + 1);
 }
if (val < min_val)
min_val = val;
}
int main()
{
int i, j, cnt, arr[MAX_N], a, b;
freopen("e:\\test\\in.txt", "r", stdin);
min_val = 0x7fffffff;
scanf("%d%d", &N, &M);
while (M--) {
scanf("%d", &cnt);
for (i = 0; i < cnt; i++) {
scanf("%d", &arr[i]);
for (j = 0; j < i; j++) {
a = arr[i];
b = arr[j];
conn[a][b] = conn[b][a] = 1;
}
}
}
for (i = 1; i <= N; i++)
bfs(i);
printf("%d\n", 100 * min_val / (N - 1));
return 0;
}
|