题目链接:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=3892&mosmsg=Submission+received+with+ID+26561660
如果边按边权的排名不变,那么最小生成树的边就不会改变,发生改变的时刻,一定有两条边边长相等
涉及解二次方程组(很重要,细节注意)
所以找出所有边长相等的时间点,并且旧边是在当前最小生成树中,新边不在,则最小生成树发生改变,重新构建最小生成树
(以后自己独立完成一遍)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;
const double eps = 1e-8;
int n, ans;
double x[maxn], y[maxn], z[maxn], vx[maxn], vy[maxn], vz[maxn];
int cnt = 0;
struct Edge{
double a, b, c;
int u, v;
bool operator < (const Edge& x) const {
return c - x.c < 0;
}
}e[maxn * maxn];
struct Event{
double t;
int newe, olde;
Event(double t=0, int newe=0, int olde=0) : t(t), newe(newe), olde(olde) {}
bool operator < (const Event& x) const {
return t - x.t < 0;
}
};
vector<Event> event;
double sqr(double x) {
return x * x;
}
void make_edges(){
cnt = 0;
for(int i = 1 ; i <= n ; ++i){
for(int j = i + 1 ; j <= n ; ++j){
double a = sqr(vx[i] - vx[j]) + sqr(vy[i] - vy[j]) + sqr(vz[i] - vz[j]);
double b = 2 * (x[i] - x[j]) * (vx[i] - vx[j]) + 2 * (y[i] - y[j]) * (vy[i] - vy[j]) + 2 * (z[i] - z[j]) * (vz[i] - vz[j]);
double c = sqr(x[i] - x[j]) + sqr(y[i] - y[j]) + sqr(z[i] - z[j]);
++cnt;
e[cnt].a = a; e[cnt].b = b; e[cnt].c = c; e[cnt].u = i; e[cnt].v = j;
}
}
sort(e + 1, e + 1 + cnt);
}
void make_event(){
event.clear();
for(int i = 1 ; i <= cnt ; ++i){
for(int j = i + 1 ; j <= cnt ; ++j){
int s1 = i, s2 = j;
if(e[s1].a - e[s2].a < 0) s1 = j, s2 = i;
double a = e[s1].a - e[s2].a;
double b = e[s1].b - e[s2].b;
double c = e[s1].c - e[s2].c;
if(fabs(a) < eps){ // bt + c = 0
if(fabs(b) < eps) continue;
if(b > 0){ swap(s1, s2); b = -b, c = -c; }
if(c > 0) event.push_back(Event(-c / b, s1, s2));
continue;
}
double delta = b * b - 4 * a * c;
if(delta < eps) continue;
delta = sqrt(delta);
double t1 = -(b + delta) / (2 * a); // solution 1
double t2 = (delta - b) / (2 * a); // solution2
if(t1 > 0) event.push_back(Event(t1, s1, s2));
if(t2 > 0) event.push_back(Event(t2, s2, s1));
}
}
sort(event.begin(), event.end());
}
int par[maxn];
void init_dsu(){
for(int i = 1 ; i <= n ; ++i) par[i] = i;
}
int find(int x){
return par[x] == x ? x : par[x] = find(par[x]);
}
int pos[maxn * maxn], re[maxn];
void solve(){
init_dsu();
memset(pos, 0, sizeof(pos));
memset(re, 0, sizeof(re));
int tot = 0;
for(int i = 1 ; i <= cnt ; ++i){ // initial MST
int u = find(e[i].u), v = find(e[i].v);
if(u != v){
par[u] = v;
++tot;
pos[i] = tot;
re[tot] = i;
}
if(tot == n - 1) break;
}
ans = 1;
for(int i = 0 ; i < event.size() ; ++i){
if(pos[event[i].olde] && (!pos[event[i].newe])){
int oldpos = pos[event[i].olde];
// rebuild MST
init_dsu();
for(int j = 1 ; j < n ; ++j){
if(j != oldpos){
int u = find(e[re[j]].u), v = find(e[re[j]].v);
if(u != v){
par[u] = v;
}
}
}
int u = find(e[event[i].newe].u), v = find(e[event[i].newe].v);
if(u != v){ // find new MST
par[u] = v;
++ans;
pos[event[i].newe] = oldpos;
re[oldpos] = event[i].newe;
pos[event[i].olde] = 0;
}
}
}
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
int kase = 0;
while(scanf("%d", &n) == 1){
cnt = 0;
for(int i = 1 ; i <= n ; ++i){
scanf("%lf%lf%lf%lf%lf%lf", &x[i], &y[i], &z[i], &vx[i], &vy[i], &vz[i]);
}
make_edges();
make_event();
solve();
printf("Case %d: %d\n", ++kase, ans);
}
return 0;
}