UVA1279,Asteroid Rangers,星际游击队,好烦的最小生成树

Posted by Cww97 on 2016-10-11

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52790482
题意:
三维空间内有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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
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<n; i++){
for (int j=i+1;j<=n;j++){
edges[++E].a = sqr(po[i].dx - po[j].dx)
+ sqr(po[i].dy - po[j].dy)
+ sqr(po[i].dz - po[j].dz);
edges[E].b = 2*( (po[i].dx - po[j].dx)*(po[i].x - po[j].x)
+(po[i].dy - po[j].dy)*(po[i].y - po[j].y)
+(po[i].dz - po[j].dz)*(po[i].z - po[j].z));
edges[E].c = sqr(po[i].x - po[j].x)
+ sqr(po[i].y - po[j].y)
+ sqr(po[i].z - po[j].z);
edges[E].from = i;
edges[E].to = j;
}
}
sort(edges + 1,edges + E + 1);
}

struct Event{
double t;//time
int newE, oldE;
Event(double t=0,int n=0,int o=0):t(t),newE(n),oldE(o){}
bool operator < (const Event &a) const {
return t < a.t;
}
};
vector <Event> events;
inline void makeEvents(){
events.clear();
for (int i=1; i<E; i++){
for (int j=i+1;j<=E;j++){
int s1 = i, s2 = j;
if (edges[s1].a < edges[s2].a) swap(s1,s2);//*****
double a = edges[s1].a - edges[s2].a;
double b = edges[s1].b - edges[s2].b;
double c = edges[s1].c - edges[s2].c;
if (fabs(a) < EPS){//b*t + c = 0
if (fabs(b) < EPS) continue;
if (b>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<EPS) continue;//no solution
delta = sqrt(delta);
double t1 = (-b-delta)/(2*a);
double t2 = (-b+delta)/(2*a);
if (t1>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<events.size();i++){
if (!pos[events[i].oldE]) continue;
if ( pos[events[i].newE]) continue;
for (int i=0; i<=n; i++) f[i] = i ;
int oldPos = pos[events[i].oldE];
for (int j = 1;j<n;j++){
if (j==oldPos)continue;
int x = F(edges[e[j]].from);
int y = F(edges[e[j]].to );
if (x != y) f[x] = y;
}
int x = F(edges[events[i].newE].from);
int y = F(edges[events[i].newE].to );
if (x == y) continue;
ans ++;
pos[events[i].newE] = oldPos;
e[oldPos] = events[i].newE;
pos[events[i].oldE] = 0;
}
return ans;
}

int main(){
//freopen("in.txt","r",stdin);
for (int cas=0;~scanf("%d",&n);){
for (int i=1;i<=n;i++)po[i].read();
makeEdges();
makeEvents();
int ans = work();
printf("Case %d: %d\n",++cas,ans);
}
return 0;
}
这里写图片描述
这里写图片描述