马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
第一题——上学
标题形貌
C 城可以视为由 n n n 个结点与 m m m 条边构成的无向图。这些结点依次以 1 , 2
, … , n 1,2
,…,n 1,2
,…,n 标号，边依次以 1 , 2
, … , m 1,2
,…,m 1,2
,…,m 标号。第 i i i 条边（ 1 ≤ i ≤ m 1≤i≤m 1≤i≤m）毗连编号为 u i u_i ui 与 v i v_i vi 的结点，长度为 l i l_i li 米。
小 A 的学校坐落在 C 城中编号为 s s s 的结点。小 A 的同砚们共有 q q q 位，他们想在包管不迟到的条件下，天天尽大概晚地出门上学。但同砚们并不会盘算从家须要多久才气到学校，于是找到了智慧的小 A。第 i i i 位同砚（ 1 ≤ i ≤ q 1≤i≤q 1≤i≤q）告诉小 A，他的家位于编号为 h i h_i hi 的结点，而且他每秒能行走 1 1 1 米。请你帮小 A 盘算，每位同砚从家出发须要多少秒才气到达学校呢？
输入格式
第一行，四个正整数 n , m , s , q n,m,s,q n,m,s,q，分别表现 C 城的结点数与边数，学校地点的结点编号，以及小 A 同砚们的数量。
接下来 m m m 行，每行三个正整数 u i , v i , l i u_i,v_i,l_i ui,vi,li，表现 C 城中的一条无向边。
接下来 q q q 行，每行一个正整数 h i h_i hi，表现一位同砚的环境。
输特别式
共 q q q 行，对于每位同砚，输出一个整数，表现从家出发到学校的最短时间。
样例
输入样例 1
- 5 5 3 3
- 1 2
- 3
- 2
- 3 2
- 3 4 1
- 4 5 3
- 1 4 2
- 5
- 1
- 4
数据范围
对于 2
0 % 2
0\% 2
0% 的测试点，包管 q = 1 q=1 q=1。
对于别的 2
0 % 2
0\% 2
0% 的测试点，包管 1 ≤ n ≤ 500 ， 1 ≤ m ≤ 500 1≤n≤500，1≤m≤500 1≤n≤500，1≤m≤500。
对于全部测试点，包管 1 ≤ n ≤ 2
× 1 0 5 ， 1 ≤ m ≤ 2
× 1 0 5 ， 1 ≤ q ≤ 2
× 1 0 5 1≤n≤2
×10^5，1≤m≤2
×10^5，1≤q≤2
×10^5 1≤n≤2
×105，1≤m≤2
×105，1≤q≤2
×105， 1 ≤ u i , v i , s , h i ≤ n ， 1 ≤ l i ≤ 1 0 6 1≤u_i,v_i,s,h_i≤n，1≤l_i≤10^6 1≤ui,vi,s,hi≤n，1≤li≤106。包管给定的图联通。
分析
这道题实在非常简朴，是一道裸的最短路题目，我们只须要从尽头出发反着跑就可以了，非常的简朴。
- #include<bits/stdc++.h>
- using namespace std;
- const int INF=2
- e5+10;
- struct Node{
- long long v,num;
- bool operator <(const Node &a)const{
- return num>a.num;
- }
- };
- vector<Node> mp[INF];
- long long dis[INF],used[INF];
- priority_queue<Node> q;
- void dijkstra(int x){
- dis[x]=0,q.push({x,0});
- while (!q.empty()){
- long long u=q.top().v;q.pop();
- if (used[u]==1)continue;
- used[u]=1;
- int len=mp[u].size();
- for (int i=0;i<len;i++){
- long long v=mp[u][i].v,w=mp[u][i].num;
- if (dis[v]>dis[u]+w){
- dis[v]=dis[u]+w;
- q.push({v,dis[v]});
- }
- }
- }
- }
- int main(){
- int n,m,s,q;
- cin>>n>>m>>s>>q;
- for (int i=1;i<=n;i++){
- dis[i]=1e18;
- }
- for (int i=1;i<=m;i++){
- long long u,v,l;
- cin>>u>>v>>l;
- mp[u].push_back({v,l});
- mp[v].push_back({u,l});
- }
- dijkstra(s);
- for (int i=1;i<=q;i++){
- int t;
- cin>>t;
- cout<<dis[t]<<endl;
- }
- return 0;
- }
最短路算法——CSDN
最短路算法——博客园
第二题——割裂
题面形貌
小杨有一棵包罗 n n n 个节点的树，此中节点的编号从 1 1 1 到 n n n。
小杨设置了 a a a 个好点对< u 1 u_1 u1, v 1 v_1 v1>,< u 2
u_2
u2
, v 2
v_2
v2
>,…,< u a u_a ua, v a v_a va>和 1 个坏点对 < b u b_u bu, b v b_v bv>。一个节点可以或许被删除，当且仅当：
删除该节点后对于全部的 i ( 1 ≤ i ≤ a ) i(1≤i≤a) i(1≤i≤a)，好点对 u i u_i ui 和 v i v_i vi 仍然连通；
删除该节点后坏点对 b u b_u bu 和 b v b_v bv 不连通。
假如点对中的恣意一个节点被删除，其视为不连通。
小杨想知道，有多少个节点可以或许被删除。
输入格式
第一行包罗两个正整数 n , a n,a n,a，寄义如题面所示。
之后 n − 1 n−1 n−1 行，每行包罗两个正整数 x i , y i x_i,y_i xi,yi，代表存在一条毗连节点 x i x_i xi 和 y i y_i yi 的边。
之后 a a a 行，每行包罗两个正整数 u i , v i u_i,v_i ui,vi，代表一个好点对 < u i , v i u_i,v_i ui,vi>。
末了一行包罗两个正整数 b u , b v b_u,b_v bu,bv，代表坏点对 < b u , b v b_u,b_v bu,bv>。
输特别式
输出一个正整数，代表可以或许删除的节点个数。
样例
输入样例
- 6 2
- 1 3
- 1 5
- 3 6
- 3 2
- 5 4
- 5 4
- 5 3
- 2
- 6
数据范围
对于全部数据，包管有 1 ≤ n ≤ 1 0 6 , 0 ≤ a ≤ 1 0 5 , u i ≠ v i , b u ≠ b v 1≤n≤10^6,0≤a≤10^5,ui≠vi,bu≠bv 1≤n≤106,0≤a≤105,ui=vi,bu=bv。
分析
这道题实在尚有颔首脑含量，根据标题，我们要知道那些点是能删的，那些点是不能删的，基于此，我们就要维护出来每个点被那些点所颠末了，大概说被颠末了频频，假如说一个点没有被任何的好点颠末，而且被坏点颠末了，那么就阐明这个点是可以被删除的，我这里说的被好点颠末指的是两个好点之间的路径哈，不要搞错了。
假如说思绪是如许的话，我们是不是就可以很显然想到一个做法，树上差分？而且这个是一个非常简答的点差分，以是说没有任何的难度好吧。
- #include<bits/stdc++.h>using namespace std;const int INF=1e6+10;vector<int> mp[INF];int dp[INF][30],deep[INF],p[INF],d[INF];void prepare(int x,int fa){ for (int i=1;(1<<i)<=deep[x]-1;i++){ dp[x][i]=dp[dp[x][i-1]][i-1]; } int len=mp[x].size(); for (int i=0;i<len;i++){ if (mp[x][i]==fa)continue; int t=mp[x][i]; dp[t][0]=x,deep[t]=deep[x]+1; prepare(t,x); }}int getroot(int x,int y){ if (deep[x]<deep[y])swap(x,y); int index=__lg(deep[x]-deep[y]); for (int i=index;i>=0;i--){ if (deep[dp[x][i]]>=deep[y])x=dp[x][i]; if (deep[x]==deep[y])break; } if (x==y)return x; for (int i=2
- 0;i>=0;i--){ if (dp[x][i]!=dp[y][i])x=dp[x][i],y=dp[y][i]; } return dp[x][0];}void get_p(int x,int fa){ int len=mp[x].size(); for (int i=0;i<len;i++){ if (mp[x][i]==fa)continue; int t=mp[x][i]; get_p(t,x); p[x]+=p[t]; }}void get_d(int x,int fa){ int len=mp[x].size(); for (int i=0;i<len;i++){ if (mp[x][i]==fa)continue; int t=mp[x][i]; get_d(t,x); d[x]+=d[t]; }}int main(){ int n,a; cin>>n>>a; for (int i=1;i<n;i++){ int u,v; cin>>u>>v; mp[u].push_back(v); mp[v].push_back(u); } deep[1]=1; prepare(1,-1); for (int i=1;i<=a;i++){ int u,v; cin>>u>>v; int root=getroot(u,v); p[u]++,p[v]++,p[root]--,p[dp[root][0]]--; } get_p(1,-1); int b1,b2
- ; cin>>b1>>b2
- ; int root=getroot(b1,b2
- ); d[b1]++,d[b2
- ]++,d[root]--,d[dp[root][0]]--; get_d(1,-1); int cnt=0; for (int i=1;i<=n;i++){ if (d[i]&&!p[i])cnt++; } cout<<cnt; return 0;}
这次的八级题不算难，只不外前面的选择题和判断题CCF堕落了，以是说延长了一点时间，对于根本比力好的人来说，这套八级的题大概是可以在1个半小时内做完的（像我这么一个蒟蒻，都只花了差不多1个小时）
3.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
发表于 2025-10-10 18:54:00