这道题写了好久……
在三维空间里面有动的点， 然后求有几次最小生成树。
其实很容易发现， 在最小生成树切换的时候，在这个时候一定有两条边相等，
而且等一下更大的那条边在最小生成树中，等一下更小的边不在最小生成树中。
这样的话过了这个时刻，等一下更小的边就会代替等一下更大的边， 从而最小生成树切换
然后我们讨论怎么实现
第一步， 建边
因为这里边的长度是随时间变化的， 所以我们可以把其写成一个二次函数。
那么显然根据两点间距离公式， 长度的平方等于x方向距离的平方+y方向距离的平方+z方向距离的平方
我们假设两个点i j
那么x方向距离的平方为当前两点x坐标相减的平方
当前的x坐标为原来的x坐标加上后来走的距离
也就是（dx是速度， x是原来的x坐标）
(edges[i].dx-edges[j].dx) * t + (edges[i].x-edges[j].x))^2
那么展开就可以得到at^2 + bt + c这样的式子
那么y方向和z方向也一样。
最终的a是三个方向的a加起来， b和c也一样
所以最后结果是这样
#define f1(a) (point[i].a - point[j].a)
#define f2(a) pow(f1(a), 2)
a =f2(dx) + f2(dy) + f2(dz)
b = 2 * (f1(dx) * f1(x) + f1(dy) * f1(y) + f1(dz) * f1(z))
c = f2(x) + f2(y) + f2(z)
然后当前边再记录起点终点。
然后我们根据开始时候的长度从小到大来排序， 等价于at^2 + bt + c中的c。
第二步， 建立事件
事件也就是开头所讲的边长度相等的时刻。
这些事件不一定都能切换最小生成树， 但切换最小生成树一定在这些事件当中。
那么怎么建立事件呢？
就暴力枚举每两条边之间是否会在某一时刻相等， 若相等则是一个事件
那么判断是否相等就是解一元二次方程了
数学问题
事件记录的是时间， 新边， 旧边
这里要注意区分新边和旧边
代码里面有注释， 这里不讲了。
第三步， 判断切换次数， 也就是答案
首先先做第一次最小生成树， 后面会切换
然后去判断新边能否代替旧的边
可以的话就更新答案。
具体看代码，注意解方程那一段最好拿纸画一下图像，因为一定要清楚哪个是
旧的边哪个是新的边，不能弄错。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 60;
const int MAXM = MAXN * (MAXN + 1) / 2;
const double EPS = 1e-8; //题目中最小单位是10^-6 struct Point
{double x, y, z, dx, dy, dz;void read() { scanf("%lf%lf%lf%lf%lf%lf", &x, &y, &z, &dx, &dy, &dz); }
}point[MAXN];struct Edge
{double a, b, c;int u, v;bool operator < (const Edge& rhs) const{return c < rhs.c;}
};
vector<Edge> edges;struct Event
{double t;int newe, olde;bool operator < (const Event& rhs) const{return t < rhs.t;}
};
vector<Event> events;int f[MAXN], n;#define f1(a) (point[i].a - point[j].a)
#define f2(a) pow(f1(a), 2)
void make_edge() //建边
{edges.clear();REP(i, 0, n)REP(j, i + 1, n)edges.push_back(Edge{f2(dx) + f2(dy) + f2(dz), 2 * (f1(dx) * f1(x) + f1(dy) * f1(y) + f1(dz) * f1(z)), f2(x) + f2(y) + f2(z), i, j}); //见解析 sort(edges.begin(), edges.end());
}#define d(x) edges[s1].x - edges[s2].x
void make_event()
{events.clear();REP(i, 0, edges.size())REP(j, i + 1, edges.size()) //以下是解二元一次方程 {int s1 = i, s2 = j;if(edges[s1].a < edges[s2].a) swap(s1, s2); //这里的s1的新边，也就是等一下会小于旧边 。规定a > 0方便后面计算 double a = d(a), b = d(b), c = d(c); //解方程中的移项 if(fabs(a) < EPS) //a等于0，也就是说变成一元一次方程 {if(fabs(b) < EPS) continue; //b=0， 那么c = 0，无解（c是原来边的长度， 肯定不等于0） if(b > 0) swap(s1, s2), b = -b, c = -c; // 规定一下b < 0，可以结合一次函数图像if(c > 0) events.push_back(Event{-c / b, s1, s2});//这样再过一会儿函数值小于0，s1 - s2 < 0continue; //所以s1是小的，是新边。 当b < 0时，只有c > 0时t的值才为正}double delta = b * b - 4 * a * c; //判别式 if(delta < EPS) continue; //判别式小于0没有实根 delta = sqrt(delta); double t1 = (-b - delta) / (2 * a); //图像与x轴的左交点 double t2 = (-b + delta) / (2 * a); //图像与x轴的右交点if(t1 > 0) events.push_back(Event{t1, s1, s2}); //注意前面规定了 a > 0 如果是左交点， 那么再过一会儿if(t2 > 0) events.push_back(Event{t2, s2, s1}); //函数值小于0，也就是s1-s2 < 0, 也就是说s1会更小， // 也就是新的边。同理右交点，s2会更小，那么s2才是新的边 }sort(events.begin(), events.end());
}int find(int x)
{if(f[x] != x)f[x] = find(f[x]);return f[x];
}int solve()
{int pos[MAXM], e[MAXN], num = 0; //pos[i]表示第i条边在最小生成树中是第几条边， 值为0表示不在最小生成树中 REP(i, 0, n) f[i] = i; //e[i]表示最小生成树中的第i条边的编号 REP(i, 0, edges.size()) pos[i] = 0;REP(i, 0, edges.size()) //先做第一次最小生成树 {int u = find(edges[i].u), v = find(edges[i].v);if(u != v){f[u] = v;e[pos[i] = ++num] = i; }if(num == n - 1) break;}int ans = 1; //等于1是因为前面做过一次了 REP(i, 0, events.size())if(pos[events[i].olde] && !pos[events[i].newe]) //旧边在最小生成树且新边不在 {REP(i, 0, n) f[i] = i;int oldpos = pos[events[i].olde];REP(j, 1, n)if(j != oldpos) //做一次没有旧边的最小生成树 {int u = find(edges[e[j]].u), v = find(edges[e[j]].v);if(u != v) f[u] = v;}int u = find(edges[events[i].newe].u), v = find(edges[events[i].newe].v); if(u != v) //如果做完后发现新边可以加进去，那么新边就可以代替旧边， 就可以替换 {ans++;pos[events[i].olde] = 0; //替换边 pos[events[i].newe] = oldpos;e[oldpos] = events[i].newe;}}return ans;
}int main()
{int kase = 0;while(~scanf("%d", &n)){REP(i, 0, n) point[i].read();make_edge();make_event();printf("Case %d: %d\n", ++kase, solve());}return 0;
}