———————————————————未完工—————————————————————前言这些题都是往年8级绿题因为本人要考8级。P14923题意n个点m条边的无向图每个点奶酪权值为C[i]猫窝位于结点 a老鼠洞位于结点 b猫和老鼠走过一条边的时间是相同的。当这个点安全当且仅当老鼠能规划一条从结点 u 出发逃往老鼠洞的路径使得对于路径上任意结点 x包括结点 u 与老鼠洞都有猫从猫窝出发到结点 x 的最短时间严格大于老鼠从结点 u沿这条路径前往结点 x 所需的时间。问能拿到安全节点的奶酪的总和。思路要推一个思路就是一个点i是安全的当前仅当dis[b-i]dis[b-a]后面做一个Dijkstra就好了。具体怎么推看题意得猫和老鼠通过一条边的时间是相同的这也就意味着只要猫能在任意一个时间点赶在老鼠从某个节点出发的必经之路前面就可以沿着老鼠本来要走的路线赶到老鼠窝前说明它是不安全的。这样就推到上面了。写个代码就好了。题解#includebits/stdc.h #define int long long using namespace std; int n,m,a,b,x,y,z,ans,res[100005],dis[100005],vis[100005]; vectorpairint,int to[100005]; struct node{ int x,s; bool operator (const nodex)const{return x.ss;} }; void dijkstra(){ priority_queuenodeq; q.push((node){b,0}); dis[b]0; while(!q.empty()){ node tq.top();q.pop(); if(vis[t.x])continue; vis[t.x]1; for(int i0;ito[t.x].size();i){ int pto[t.x][i].first,sto[t.x][i].second; if(dis[p]dis[t.x]s){ dis[p]dis[t.x]s; if(!vis[p])q.push((node){p,dis[p]}); } } } } signed main(){ cinnmab; memset(dis,0x3f,sizeof dis); for(int i1;in;i)cinres[i]; for(int i1;im;i){ cinxyz; to[x].push_back(make_pair(y,z)); to[y].push_back(make_pair(x,z)); } dijkstra(); for(int i1;in;i){ if(dis[i]dis[a])ansres[i]; } coutans\n; }P11967题意思路题解P10289题意n个点n-1条边无向图经过一条边要用1单位时间k个城市每两个互相传送不需要时间q次询问问从s到t最短时间是多少。思路不难发现从s到t要么用LCA判断最近公共祖先直接走要么通过bfs传送门距离s最近的到距离t最近的距离两种情况取一个最小值这道题就完成了。题解#includebits/stdc.h using namespace std; int n,k,Q,x,y,dis[200005],d[200005],fa[200005][25]; vectorint to[200005]; queueint q; void dfs(int x,int f,int step){ fa[x][0]f; for(int i1;i20;i) fa[x][i]fa[fa[x][i-1]][i-1]; d[x]step; for(int i0;ito[x].size();i){ int yto[x][i]; if(yf)continue; dfs(y,x,step1); } } void bfs() { while(!q.empty()){ xq.front();q.pop(); for(int i0;ito[x].size();i){ yto[x][i]; if(dis[y]0x3f3f3f3f){ dis[y]dis[x]1; q.push(y); } } } } int LCA(int x,int y){ if(d[x]d[y])swap(x,y); for(int k20;k0;k--) if(d[fa[x][k]]d[y])xfa[x][k]; if(xy)return x; for(int k20;k0;k--){ if(fa[x][k]!fa[y][k])xfa[x][k],yfa[y][k]; } return fa[x][0]; } int main(){ memset(dis,0x3f,sizeof dis); cinnkQ; for(int i1;in;i){ scanf(%d%d,x,y); to[x].push_back(y); to[y].push_back(x); } dfs(1,0,1); for(int i1;ik;i)cinx,q.push(x),dis[x]0; bfs(); while(Q--){ cinxy; coutmin(dis[x]dis[y],d[x]d[y]-2*d[LCA(x,y)])\n; } }P10725题意n节点每个节点要么是黑色要么是白色求相距最远的一对不同颜色节点的距离是多少。思路f[x][0/1]表示从x往下最远的白/黑颜色点f[x][0]max(f[x][0],f[y][0]1)f[x][1]max(f[x][1],f[y][1]1)其中x为y的父结点。怎么推导的就是x-k和y-kx-yk是下面最远的白/黑点而ansmax(max(f[x][0]f[y][1]1,f[x][1]f[y][0]1),ans)最后写个树形dp就好了。注意千万不要在dfs时定义全局变量被卡了好久题解#includebits/stdc.h using namespace std; int n,a[100005],f[100005][2],ans; vectorint to[100005]; void dfs(int x,int fa){ f[x][0]f[x][1]-0x3f3f3f3f; f[x][a[x]]0; for(int i0;ito[x].size();i){ int yto[x][i]; // if(x3)couty\n; if(yfa)continue; dfs(y,x); // if(x3)couty f[y][0] f[y][1]\n; ansmax(max(f[x][0]f[y][1]1,f[x][1]f[y][0]1),ans);//取不同颜色 f[x][0]max(f[x][0],f[y][0]1);//转移方程 f[x][1]max(f[x][1],f[y][1]1); } // coutx f[x][0] f[x][1]\n; return; } int main(){ int x,y; cinn; for(int i1;in;i)cina[i]; for(int i1;in;i){ cinxy; to[x].push_back(y); to[y].push_back(x); } dfs(1,0); coutans\n; }P13019题意思路题解P13020题意思路题解P10726题意思路题解P10264题意思路题解P14924题意思路题解总结终于完结撒花了