首页 > 代码库 > SGU 164.Airline
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;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。