SGU 164.Airline（结论题）

时间限制：0.25s

空间限制:4M

题意：

在n（1<=n<=200）个点的无向完全图中，有m种不同的边.现在从中选择不超过（m+1)/2种边，使得任意两点可以通过不超过3条边互相到达。

Solution：

将无向完全图的边分成两部分，那么一定有一部分所有点的最短距离不超过3。

暂时没有较好的证明办法。。。 -_-!

code

取1~m/2为一组，m/2+1~m为一组,Floyd判断第一组是否满足要求,如果满足输出第一组,不满足输出第二组.

#include <cstdio>

const int INF = 300 + 9;

int g[INF][INF], f[INF][INF];

int n, m, i, j, k, t;

int main() {

	scanf ("%d%d", &n, &m);

	t = (m + 1) >> 1;

	for (i = 1; i <= n; ++i)

		for (j = 1; j <= n; ++j) {

			scanf ("%d", g[i] + j);

			f[i][j] = g[i][j] <= t ? 1 : INF;

		}

	for (k = 1; k <= n; ++k)

		for (i = 1; i < n; ++i)

			for (j = i + 1; j <= n; ++j)

				if (f[i][k] + f[j][k] < f[i][j])

					f[i][j] = f[j][i] = f[i][k] + f[j][k];

	for (i = 1; i < n; ++i)

		for (j = i + 1; j <= n; ++j)

			if (f[i][j] > 3) {

				printf ("%d\n", m - t);

				for (++t; t <= m; ++t)   printf ("%d ", t);

				putchar (10);

				return 0;

			}

	printf ("%d\n", t);

	for (i = 1; i <= t; ++i)  printf ("%d ", i);

	putchar (10);

	return 0;

}