时间限制：0.25s

空间限制:4M

题意：

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

 

 

 

 

---

 

Solution：

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

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

              

                         

code

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

 

#include 
     
      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;}