题意：

三维空间内有n（n<=50）个点，每个点有初始坐标和xyz和xyz三个方向上的速度dxdydz

求最小生成树变化的次数

分析：

最多啊n^2条边，最小生成树变化，无非是原来生成树中的某条边被新边替换

所以对每两条边计算可能出现这两条边相等的时间，称之为一个Event，（n^4个）

此时生成树可能会发生变化，对每个Event检查最小生成树有没有发生变化

总复杂度n^6，会炸

优化：对每个Event看这个时间点的两条相等的边（一条上升趋势A一条下降趋势B）

如果A在当前的生成树里面，则重新搞出生成树复杂度n^2，

这样可以减少切换次数，可以卡过去（lrj的分析= =）

流程：

首先读进去点，每个点6个参数，构造边Edges，//makeEdges

然后构造Events事件时间点，sort//makeEvents

构造初始状态的最小生成树//work

对每个时间点如果当前生成树上有边是此时的oldEdge，//work

则更新生成树//EndWork

代码有点长，有点烦，结构体多不要嫌烦，

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N = 9999;const double EPS = 1e-6;int n;struct point{ double x,y,z,dx,dy,dz; inline void read(){ scanf("%lf%lf%lf%lf%lf%lf",&x,&y,&z,&dx,&dy,&dz); }}po[N];struct Edge{ double a,b,c; int from,to; bool operator < (const Edge &a)const{ return c < a.c; }}edges[N];int E;inline double sqr(double x){ return x*x;}inline void makeEdges(){ E = 0; for (int i=1; i
           
             events;inline void makeEvents(){ events.clear(); for (int i=1; i
            
             0){swap(s1,s2);b=-b;c=-c;} if (c>0) events.push_back(Event(-c/b,s1,s2)); }else { double delta = b*b - 4*a*c; if (delta
             
              0)events.push_back(Event(t1,s1,s2)); if (t2>0)events.push_back(Event(t2,s2,s1)); } } } sort(events.begin(),events.end());}int f[N], pos[N], e[N];int F(int x){ return f[x]==x?x:f[x]=F(f[x]);}inline int work(){ for (int i=0;i<=n;i++)f[i]=i; memset(pos, 0, sizeof(pos)); int cnt = 0; for (int i=1;i<=E;i++){ //kruskal int x = F(edges[i].from); int y = F(edges[i].to ); if (x==y) continue; //printf("edge:%d-%d\n",edges[i].from,edges[i].to); f[x] = y; e[pos[i]=++cnt] = i; if (cnt==n-1)break; } int ans = 1; for (int i=0;i