练习题 - Geodetic集合(图论)

前言

算法拾遗继续。

题目

问题描述

图G是一个无向连通图,没有自环,并且两点之间至多只有一条边。我们定义顶点v,u最短路径就是从v到u经过边最少的路径。所有包含在v-u的最短路径上的顶点被称为v-u的Geodetic顶点,这些顶点的集合记作I(v, u)。
我们称集合I(v, u)为一个Geodetic集合。
例如下图中,I(2, 5)={2, 3, 4, 5},I(1, 5)={1, 3, 5},I(2, 4)={2, 4}。

给定一个图G和若干点对v,u,请你分别求出I(v, u)。

输入(geo.in)

第一行两个整数n,m,分别表示图G的顶点数和边数(顶点编号1-n)
下接m行,每行两个整数a,b表示顶点a和b之间有一条无向边。
第m+2行有一个整数k,表示给定的点对数。
下接k行,每行两个整数v,u。

输出(geo.out)

共k行,每行对应输入文件中每一个点对v,u,按顶点编号升序输出I(v, u)。同一行的每个数之间用空格分隔。

样例 geo.in

5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4

geo.out

2 3 4 5
1 3 5
2 4

数据范围

100%的数据,n<=40

解答

本题考察图的有关知识。算法就是从每个点出发进行BFS扩展,按得到的BFS序列进行递推 设 min[i, j]为从i到j的最短路长度 设f[i, j]表示从i到j点的最短路覆盖的节点集合, f[i, j] = f[i, k] U {j} k={1..n} and (min[i, k]+1=min[i, j])and (k,j)存在 对于输入的每个v,u对,输出f[v,u]中的所有点就可以了。

实际上,个人认为图论中Floyed算法的运用。

#include <stdio.h>
#define MAX 1000000000

FILE *in, *out;
int m, n, k, dis[42][42], p[42][42];

void floyed() {
  int i, j;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      if (!p[i][j])
        p[i][j] = MAX;

  int t;
  for (t = 1; t <= n; t++)
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        if (p[i][j] > p[i][t] + p[t][j])
          p[i][j] = p[i][t] + p[t][j];
}

void swap(int i, int j, int x[]) {
  int tem;
  tem = x[i];
  x[i] = x[j];
  x[j] = tem;
}

void paixu(int x[], int len) {
  int i, j;
  for (i = 0; i < len - 1; i++)
    for (j = i + 1; j < len; j++)
      if (x[j] < x[i])
        swap(i, j, x);
}

void fsearch(int x, int y) {
  int ans[40] = {0}, wz = 0, i;
  ans[wz++] = x;
  ans[wz++] = y;
  for (i = 1; i <= n; i++)
    if (p[x][i] + p[i][y] == p[x][y])
      ans[wz++] = i;
  paixu(ans, wz);

  for (i = 0; i < wz; i++)
    fprintf(out, "%d ", ans[i]);
  fprintf(out, "\n");
}

int main() {
  int i, j, x, y;
  in = fopen("geo.in", "r");
  out = fopen("geo.out", "w");
  fscanf(in, "%d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    fscanf(in, "%d%d", &x, &y);
    dis[x][y] = dis[y][x] = p[x][y] = p[y][x] = 1;
  }

  floyed();

  fscanf(in, "%d", &k);
  for (i = 1; i <= k; i++) {
    fscanf(in, "%d%d", &x, &y);
    fsearch(x, y);
  }

  fclose(in);
  fclose(out);

  return 0;
}

参考


* cached version, generated at 2018-12-11 23:34:46 UTC.

Subscribe by RSS