Asteroid Rangers UVA - 1279（动态最小生成树）

Asteroid Rangers UVA - 1279

题意：

给你一个动态最小生成树。
问：
这棵生成树，改变了几次。

思路:（紫薯）

1. 不难发现：最小生成树切换的时刻一定对应着某两条边。且这两条边的权值相等。一共有O（$n^2$）条边，因此有O（$n^4$）种可能的切换时间（称为事件点）。
2. 最容易想到的是把所有可能的事件点按照从小到大排序，依次计算每个事件时间点之后0.5*$10^{-6}$时刻的最小生成树（题目保证了最小生成树是不会发生变化的），判断它是否和上一个最小生成树相等。假设使用了O（$n^2$）时间复杂度的prim算法。总时间复杂度为O（$n^6$），需要优化。
3. 优化：假如一个事件点，对应的两条边e1和e2相等。只有当两者其中有一条在现在的最小生成树里，且该事件点之后这条边会变得比另一条边大时，才有可能发生转换。

反思：

1. 由时间和距离可以得到，事件的时间是一个二次函数，处理时要小心一点。保证开口向上。且要保证存在（注意好讨论）

AC

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define fori(i,x,y) for(int i=(x); i<(y); i++)
#define mst(x, a) memset(x,a,sizeof(x))
using namespace std;
const int maxn = 50 + 5;
const double eps = 1e-8;
struct point{
    int x, y, z, dx, dy, dz;
} p[maxn];
struct EDGE{
    int a, b, c;
    int u, v;
    bool operator< (const EDGE& x)const{
        return c < x.c;
    }
}edges[maxn*maxn];
struct EVENT{
    double t;
    int olde;
    int newe;
    bool operator < (const EVENT& x)const {
        return t<x.t;
    }
}event[2*maxn*maxn*maxn*maxn];
int mul(int i, int j) { return (i-j)*(i-j);}
int n;
int tot1 = 0, tot2 = 0;
void init(){
    tot1 = 0, tot2 = 0;
    int x, y, z, dx, dy, dz;
    For(i,1,n){
        cin>>x>>y>>z>>dx>>dy>>dz;
        p[i]={x, y, z, dx, dy, dz};
    }
}
void build(){
    For(i,1,n){
        For(j,i+1,n){
            EDGE e;
            e.a = mul(p[i].dx, p[j].dx) + mul(p[i].dy, p[j].dy) + mul(p[i].dz, p[j].dz);
            e.b = 2 * ((p[i].x - p[j].x) * (p[i].dx -  p[j].dx) + (p[i].y -  p[j].y) * (p[i].dy - p[j].dy) + (p[i].z - p[j].z)*(p[i].dz - p[j].dz));
            e.c = mul(p[i].x, p[j].x) + mul(p[i].y, p[j].y) + mul(p[i].z, p[j].z);
            e.u = i; e.v = j;
            edges[tot1++] = e;
        }
    }
    sort(edges, edges + tot1);
    fori(i,0,tot1){
        fori(j,i+1,tot1){
            int s1 = i, s2 = j;
            int a = edges[i].a - edges[j].a;
            int b = edges[i].b - edges[j].b;
            int c = edges[i].c - edges[j].c;
            if(a < 0) { a = -a; c = -c; b = -b; swap(s1,s2);}
            if(a == 0){//fabs(a) < eps)
                if(b == 0) continue;
                if(b > 0) {b = -b; c = -c; swap(s1,s2);}//b>0, 同时取负.
                if(c > 0) {double t = (double)c/(double)(-b); event[tot2++] = {t, s2, s1};}
                continue;
            }
            double delta = b*b - 4*a*c;
            if(fabs(delta) < 0)continue;
            delta = sqrt(delta);
            double t1 = (delta - b) / (double)(2*a);
            double t2 = (-delta - b) / (double)(2*a);
            if(t1>0)event[tot2++] = {t1, s1, s2};
            if(t2>0)event[tot2++] = {t2, s2, s1};
        }
    }
    sort(event, event+tot2);
}
int f[maxn], order[maxn];
int find(int x){
    if(x == f[x])return x;
    return f[x] = find(f[x]);
}
int solve(){
    int ans = 1;
    For(i,1,n)f[i] = i;
    int u, v, a, b;
    int cnt = 1;
    int idx = 0;
    mst(order,0);
    fori(i,0,tot1){
        u = edges[i].u; v = edges[i].v;
        a = find(u), b =find(v);
        if(a == b) continue;
        f[a] = b;
        cnt++;
        order[idx++] = i;
        if(cnt == n)break;
    }
    fori(i,0,tot2){
        double t = event[i].t;
        int newe = event[i].newe;
        int olde = event[i].olde;
        For(j,1,n)f[j] = j; cnt = 1;
        int pos = 0, vis = false;
        fori(j,0,idx)if(order[j] == newe) vis= true;
        if(vis)continue;/// olde and newe isn't in a same set
        fori(j,0,idx){
            if(order[j] == olde){
                pos = j;
                continue;
            }
            u = edges[order[j]].u; v = edges[order[j]].v;
            a = find(u); b = find(v);
            if(a == b)continue;
            f[a] = b;
            cnt++;
            if(cnt == n)break;
        }
        u = edges[newe].u; v = edges[newe].v;
        a = find(u); b = find(v);
        if(a != b && ++cnt == n){
            order[pos] = newe;
            ans++;
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int kase = 0;
    while(cin>>n){
        init();
        build();
        cout<<"Case "<<++kase<<": "<<solve()<<endl;
    }
    return 0;
}