UVa1279

题目链接

题意

在三维空间中给出50个匀速移动的点。求最小生成树会改变多少次。

思路

最小生成树的转换一定伴随着有两条边的长度相同，我们记录所有的边\(O(n^2)\).可能出现的边长度相同的事件有\(O(n^4)\)。
一种想法是对于每一个事件，计算单位时间前的最小生成树与现在的最小生产树是否相同。时间复杂度达到了\(O(n^6)\).很明显是超时了。
我们可以优化为，当一个边权事件产生时。边权在之后较大的边在当前的最小生成树中，边权较小的边在新产生的最小生成树中。此时时间可以满足要求。
对于判断新边是否在生成树中，我们将之前所有的边除去那条将要变大的事件边，之后对剩下的边进行最小生成树。此时判断新边的两个点是否在不同的岛中，如果在不同的岛中，则新边为最少生成树中的一条边。
对于长度在不断变换的边，我们经过换算之后可以用 \(len = at^2 + b^t + c\),表示。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
const int maxn = 55;
const int maxm = maxn * (maxn+1)/2;
const int INF = 1e9+3;
const double eps = 1e-8;

int n, nks;
int pa[maxn];

void init()
{
	for(int i  =0 ; i < n;++i)
		pa[i]  = i;
}

int find(int x) { return pa[x] != x ? pa[x] = find(pa[x]) : x;}


struct Event 
{
	double t;
	int newks, oldks;
	Event(double t = 0, int newks = 0, int oldks = 0) : t(t), newks(newks), oldks(oldks) {}
	bool operator < (const Event & rhs) const {
		return t - rhs.t < 0;
	}
};

vector<Event> events;

struct Point
{
	double x, y , z;
	double vx, vy, vz;
};

Point kp[maxn];

struct Segment
{
	double a, b, c;
	int u ,v;
	bool operator < (const Segment & rhs) const {
		return c - rhs.c <0;
	}
} ks[maxm]; 

double sqr(double x) {return x * x;}

void make_seg()
{
	nks = 0;
	for(int i = 0 ; i<n;++i)
		for(int j = i+1;j<n;++j)
		{
			ks[nks].a = sqr(kp[i].vx - kp[j].vx) + sqr(kp[i].vy - kp[j].vy) + sqr(kp[i].vz - kp[j].vz);
			ks[nks].b = 2 * ((kp[i].vx - kp[j].vx ) * (kp[i].x - kp[j].x) +(kp[i].vy - kp[j].vy ) * (kp[i].y - kp[j].y) +(kp[i].vz - kp[j].vz ) * (kp[i].z - kp[j].z)   );
			ks[nks].c  = sqr(kp[i].x - kp[j].x) + sqr(kp[i].y - kp[j].y) + sqr(kp[i].z - kp[j].z);
			ks[nks].u = i;
			ks[nks].v = j;
			//printf("a = %lf, b = %lf, c  = %lf, u  =%d, v = %d\n", ks[nks].a,ks[nks].b,ks[nks].c,ks[nks].u,ks[nks].v );

			nks++;
		}
	sort(ks, ks+nks);
}

void make_event()
{
	//printf("nks = %d\n", nks);
	events.clear();
	for(int i = 0; i < nks; ++i)
	for(int j  =i+1;j <nks;++j)
	{
		int s1 = i , s2  =j;
		if(ks[s1].a - ks[s2].a < 0) s1 = j, s2   = i;

		double a = ks[s1].a - ks[s2].a;
		double b = ks[s1].b - ks[s2].b;
		double c = ks[s1].c - ks[s2].c;
		if(fabs(a) < eps) {
			if(fabs(b) < eps) continue;
			if(b > 0) {swap(s1, s2); b  =- b;c = -c;}//b>0此时s1 之后会大于s2因此我们交换位置
			if(c >  0) events.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);
		double t2  =(  delta - b) / (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 calc()
{
	int pos[maxm];
	int e[maxn];
	init();
	for(int i  =0; i < nks;++i) pos[i] =  0;
	int idx = 0;
	for(int i = 0 ;i <nks;++i) {
		int u = find(ks[i].u), v = find(ks[i].v);
		if(u!=v) {
			e[pos[i] = ++idx] = i;
			pa[u] =v;
		}
		if(idx == n-1) break;
	}

	int ans = 1;
	//printf("events.size() = %d\n", events.size());

	for(int i  =0 ; i < events.size();++i) {
		if(pos[events[i].oldks] && (!pos[events[i].newks])) {
			init();
			int oldpos = pos[events[i].oldks];
            //将旧边剔除，对于剩下的边进行生成树，此时一定无法形成一个联通图
			for(int j  =1 ;j < n ; ++j) {
				if(j!=oldpos) {
					int u  =find(ks[e[j]].u) , v = find(ks[e[j]].v);
					if(u !=v ){ pa[u] =v; }
				}
			}
            //新边的两个点在不同联通图中，说明将新边作为生成树，会形成联通图
			int u = find(ks[events[i].newks].u), v = find(ks[events[i].newks].v);
			if(u !=v) {
				ans ++;
				pos[events[i].newks] = oldpos;
				e[oldpos] = events[i].newks;
				pos[events[i].oldks] = 0;
			}

		}
	}
	return ans;

}



int solve()
{
	for(int i = 0 ;i <n;++i)
	{
		cin >> kp[i].x >> kp[i].y >> kp[i].z >> kp[i].vx >> kp[i].vy >> kp[i].vz;
	}
	make_seg();
	make_event();
	return calc();
}




int main()
{
	int cnt_all = 0;
	while(cin >> n)
	{
		cnt_all++;
		printf("Case %d: %d\n", cnt_all, solve());
	}
}

紫书 UVa1279

原文：https://www.cnblogs.com/MoYuMaster/p/15345025.html