NOIP 2018训练赛第二场

本文主要是介绍NOIP 2018训练赛第二场，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

A. inform

一场天灾过后，B 市的所有主干道路都被切断了。灾后重建的一项重要任务是恢复通信。B 市共有 nn 个关键的据点，而我们现在有一条关键的消息，需要所有的据点都要收到。

消息的传递有两种方式：

空降：可以直接将消息传给某个据点，每次需要的代价为 vv。

通信员：可以将消息从一个据点传到另一个据点，需要的代价为两个据点在地图上的欧氏距离的平方。保证所有点的坐标均为整数，所以这个代价也一定是整数。

注意，通信员只能从已有消息的据点传递消息到另一个据点。所以，至少第一个收到消息的据点一定是通过空降的。

在保证所有的据点都收到消息的前提下，最小的总代价是多少？

所有测试点的 n 分别为：1, 5, 9, 13, 17, 50, 300, 1000, 3000, 5000。

对于所有数据，保证 0≤v≤100,000,0≤x,y≤30,0000≤v≤100,000,0≤x,y≤30,000。

很明显，n的平方的最小生成树可以通过此题，prim即可。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;int n,k;
int r[5010][5010];
int first[5010];
long long dis[5010];
bool tf[5010];
struct node{long long x,y;
}p[5010];
int len=0;
int d[5010];int main(){scanf("%d %d",&n,&k);for(int i=1;i<=n;i++) scanf("%d %d",&p[i].x,&p[i].y);int temp;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){temp=(p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y);r[i][j]=r[j][i]=temp;}dis[1]=0;tf[1]=true;for(int i=2;i<=n;i++) dis[i]=r[1][i];int tot=2;int mmin=2e9,id;long long ans=k;while(tot<=n){mmin=2e9;for(int i=1;i<=n;i++) if(tf[i]==false && dis[i]<mmin) mmin=dis[i],id=i;tf[id]=true;tot++;if(dis[id]>k) ans+=k;else ans+=dis[id]; for(int i=1;i<=n;i++) if(tf[i]==false) dis[i]=min(dis[i],(long long)r[id][i]);}printf("%lld\n",ans);
}

B. treelink

D 国有 nn 个城市，有若干条道路，每条道路能连接两个城市，并且有一定的长度。

可是……初始时，并没有任何道路存在。接下来，有 qq 个操作需要你依次完成：

x y 表示：询问城市 xx 与 yy 之间的最短路径长度；如果不存在任何路径，则你应当回答-1。

x y w 表示：在城市 xx 与 yy 之间修建了一条长度为 ww 的道路。保证在此之前在城市 xx 与 yy 之间不存在任何路径（即：假如在此之前给出一个 xx yy 的操作，保证其答案应当为-1）。

离线，对于每一条边，我们记录下他加入的时间和长度。

然后，如果当前的查询没有超过这条链建立的时间，那么就输出，否则就是-1.

但是，虽然标程是nlogn的，但是我的两个log还是卡了过去。

就是直接启发式合并，然后维护lca，所以加一条边是两个log的，查询是一个log的，就是比较慢。在比赛中我却因为要卡常改了一些东西，然后就错了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;int n,q;
char a[110];
struct ques{int x,y,w;
}p[500010];
struct edge{int y,next,c;
}s[1000010];
int l=0;
int size[500010],fa[500010],dep[500010],first[500010],dis[500010];
int f[500010][20];
int len=0;void ins(int x,int y,int c){len++;s[len].y=y;s[len].c=c;s[len].next=first[x];first[x]=len;
}void update(int y,int x,int c){dis[y]=dis[x]+c;dep[y]=dep[x]+1;f[y][0]=x;for(int k=1;k<=19;k++) f[y][k]=f[f[y][k-1]][k-1];
}void dfs(int x){for(int i=first[x];i!=0;i=s[i].next){int y=s[i].y;if(y!=f[x][0]){update(y,x,s[i].c);dfs(y);}}
}int lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=19;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}int get_ans(int x,int y){return dis[x]+dis[y]-2*dis[lca(x,y)];
}int findpa(int x){if(fa[x]!=x) return fa[x]=findpa(fa[x]);return x;
}int main(){scanf("%d %d\n",&n,&q);for(int i=1;i<=n;i++) size[i]=1,fa[i]=i;int x,y,w,now;int tot=0;//询问总数 bool tf=false;for(int i=1;i<=q;i++){gets(a+1);l=strlen(a+1);x=y=w=now=0;for(int k=1;k<=l;k++){if(a[k]!=' ') now=now*10+a[k]-'0';else{if(x==0) x=now;else if(y==0) y=now;else if(w==0) w=now;now=0;}}if(y==0) y=now;else if(w==0) w=now;p[i].x=x;p[i].y=y;p[i].w=w;		if(w==0) tot++;}for(int i=1;i<=q;i++){if(p[i].w==0 && !tf) {printf("-1\n");if(tot==i) return 0;continue;}tf=true;if(p[i].w==0) {if(findpa(p[i].x)==findpa(p[i].y)) printf("%d\n",get_ans(p[i].x,p[i].y));else printf("-1\n");}else {int fx=findpa(p[i].x),fy=findpa(p[i].y);if(size[fx]<size[fy]) swap(p[i].x,p[i].y),swap(fx,fy);fa[fy]=fx;size[fx]+=fy;update(p[i].y,p[i].x,p[i].w);ins(p[i].x,p[i].y,p[i].w);ins(p[i].y,p[i].x,p[i].w);dfs(p[i].y);}}
}