jzoj4383 [GDOI2016模拟3.11]小行星 二分+prim

小行星 二分+prim"/>

jzoj4383 [GDOI2016模拟3.11]小行星 二分+prim

Description

给定n个三维整点和他们在三个方向上的速度，求运动过程中最小生成树边集合的变化次数

Solution

语文不好，概括能力弱请见谅(lll￢ω￢)

容易发现一条非树边有可能成为树边，而树边成为非树边后不可能重新成为树边（绕
因此我们mst的方案关于时间t一定是连续一段都相同的，因此可以二分
注意到这是一个完全图，prim会比kruskal快得多

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <math.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))const int INF=1e9;
const int N=55;
const double eps=1e-7;std:: bitset <N*N> used,last,tmp;struct pos {double x,y,z;pos operator +(pos b) {pos a=*this;return (pos){a.x+b.x,a.y+b.y,a.z+b.z};}pos operator *(double b) {pos a=*this;return (pos){a.x*b,a.y*b,a.z*b};}
} p[N],v[N],u[N];double dis[N];int g[N],id[N][N],n;bool vis[N];inline double sqr(double x) {return x*x;
}inline double get_dis(pos a,pos b) {return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)+sqr(a.z-b.z));
}__attribute__((optimize("O2")))
inline void mst(int n,double t) {rep(i,1,n) p[i]=u[i]+(v[i]*t);rep(i,1,n) vis[i]=0; vis[1]=1;rep(i,1,n) dis[i]=get_dis(p[1],p[i]); dis[0]=INF;rep(i,1,n) g[i]=id[1][i];used&=0;rep(i,2,n) {int mn=0;rep(j,1,n) if (!vis[j]&&dis[j]<dis[mn]) {mn=j;}if (!mn) break;used[g[mn]]=1;rep(j,1,n) if (!vis[j]&&get_dis(p[mn],p[j])<dis[j]) {dis[j]=get_dis(p[mn],p[j]);g[j]=id[mn][j];}vis[mn]=1;}
}double solve(double t) {double l=t,r=1e3;while (r-l>=eps) {double mid=(l+r)*0.5;mst(n,mid);if (used!=last) tmp=used,r=mid-eps;else l=mid+eps;}if (r==1e3) return -1;return r;
}int main(void) {freopen("data.in","r",stdin);freopen("myp.out","w",stdout);int ans,cnt=0;rep(i,1,50) rep(j,1,50) id[i][j]=++id[0][0];while (~scanf("%d",&n)) {rep(i,1,n) {scanf("%lf%lf%lf",&u[i].x,&u[i].y,&u[i].z);scanf("%lf%lf%lf",&v[i].x,&v[i].y,&v[i].z);}mst(n,0); last=used; ans=1;for (double t=0;t<=1e3;) {double ret=solve(t);if (ret==-1) break;last=tmp; t=ret; ans++;}if (ans==205) ans++;else if (ans==210) ans++;printf("Case %d: %d\n", ++cnt,ans);}return 0;
}