『jzyzoj』 Geodetic集合

发表于 | 阅读次数:
字数统计: 875 字

这是一道图论题：

题面：

图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)。

输入格式

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

输出格式

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

样例输入

1
2
3
4
5
6
7
8
9
10
11
5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4

样例输出

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

思考

关于这道题果断floyd，因为数据大小才40，但是发现一个问题就是我不会存路径… 赶紧学了一下存路径但是才发现题目并不是在求最短路，因为这个图中可能会有很多条最短路，他要求的是所有最短路路上的点，于是我又做了了一下求所有可以使路径变短的点，可惜还不对，最后才发现只要求一边最短路，然后再枚举中间点，看是否等于最短路，并且把这个点保存下来。于是艰难AC。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#define INF 99999999
#define MAXN 100
#define ll long long 
using namespace std;

int n=0,m=0;
int path[MAXN][MAXN][MAXN];
int dis[MAXN][MAXN];
int u=0, v=0;
int l[MAXN],len=0;

inline int Read()
{
	int Num=0, F=1;  char ch=getchar();
	while (!isdigit(ch))  {  if (ch == '-') F=-1; ch=getchar();  }
	while ( isdigit(ch))  {  Num=(Num<<1)+(Num<<3)+ch-'0';  ch=getchar();  }
	return Num*F;
}

void init()
{
	n=Read();  m=Read();
	int x=0, y=0;
	for (int i=1;i<=n;++i)
	    for (int j=1;j<=n;++j)
	        dis[i][j]= (i == j) ? 0 : INF;
    memset(path, 0, sizeof(path));
	for (int i=1;i<=m;++i)
	{
		x = Read();
		y = Read();
		dis[x][y] = 1;
		dis[y][x] = 1;
	}
}

void Floyd()
{
	for (int k=1;k<=n;++k)
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
    		    if (dis[i][j] > dis[i][k]+dis[k][j])
    		    {
        			dis[i][j] = dis[i][k]+dis[k][j];
        			path[i][j][++path[i][j][0]] = k;
    		    }
}

void dfs(int i, int j)//  输出路径
{
    if (path[i][j] > 0)
    {
        dfs(i, path[i][j]);
        printf("%d ",path[i][j]);
        dfs(path[i][j], j);
    }
}

int main()
{
	init();
	Floyd();
	int t=Read();
	for (int i=1;i<=t;++i)
	{
	    memset(l, 0, sizeof(l));
	    len=0;
		u=Read();
		v=Read();
		path[i][j][++path[i][j][0]]=u;
		path[i][j][++path[i][j][0]]=v;
	    sort(path[u][v]+1,path[u][v]+1+path[u][v][0]);
	    for (int i=1;i<=path[u][v][0]; ++i)
	        printf("%d ",path[u][v][i]);
		printf("\n");
	}
	return 0;
}