)
第一篇题解
蒟蒻的第四篇题解希望大家支持
题目描述
- P3915树的分解
P3915 树的分解
题目描述
给出N NN个点的树和K KK，问能否把树划分成N K \frac{N}{K}KN个连通块，且每个连通块的点数都是K KK。
输入格式
第一行，一个整数T TT，表示数据组数。接下来T TT组数据，对于每组数据：
第一行，两个整数N , K N, KN,K。
接下来N − 1 N - 1N−1行，每行两个整数A i , B i A_i, B_iAi,Bi，表示边( A i , B i ) (A_i, B_i)(Ai,Bi)。点用1 , 2 , … , N 1, 2, \ldots, N1,2,…,N编号。
输出格式
对于每组数据，输出YES或NO。
输入输出样例 #1
输入 #1
2 4 2 1 2 2 3 3 4 4 2 1 2 1 3 1 4输出 #1
YES NO说明/提示
- 对于60 % 60 \%60%的数据，1 ≤ N , K ≤ 1 0 3 1 \le N, K \le 10^31≤N,K≤103；
- 对于100 % 100 \%100%的数据，1 ≤ T ≤ 10 1 \le T \le 101≤T≤10，1 ≤ N , K ≤ 1 0 5 1 \le N ,K \le 10^51≤N,K≤105。
思路分析
这是一道有关于树的遍历的题目，和树相关的题目我们一般采用递归实现。在树当中联通块的意思其实就是包括某一个根节点和其所有子节点的一棵子树，这题我们就是要将一整棵树一片片地分解开来，以某一个节点为根节点进行分析，会遇到一下这三种情况1.以该节点为根节点的子树所包括的总节点数小于k，2.以该节点为根节点的子树所包括的节点总数等于k，3.以该节点为根节点的总结点数大于k，接下来我们分别分析这三种情况该如何处理
- 1.总节点数不足k个，那么就把这个部分子树并到该根节点的父节点上，返回总节点数
- 2.总节点数刚好为k，那么这个部分作为一个连通块直接划掉即可，返回0
- 3.总节点数大于k，说明这个一整棵子树无法分成N/K个联通块，返回-1，即输出一个标记失败情况的数字
可能出现的疑惑
不知道有同学是否会这样想，以该节点为根节点的总节点个数大于k为什么就能判断整棵数不能分成N/K个联通块呢，为什么不能把部分节点分给其他子树呢？
有这个疑惑的同学，认真思考了这个问题，现在做出解答。
因为我们看问题的方式太片面了，我们想一想为什么这个以这个节点为根节点的总节点数会大于k呢，那当然是因为该节点的叶子节点返回了过多的点，这看上去是一句废话，但要好好理解，一个通俗的解释方式，该节点的叶子节点解决不了自己的问题，就去向该节点寻求帮助，但是寻求帮助以后，该节点就无法解决自身的问题（因为总节点数超过k），对于叶子节点来说，他自己解决不了问题（数量不足k个），向上寻求帮助也解决不了问题，那么这个节点的问题无论如何也解决不了（即无论如何也不能凑出k个节点）
给出一个案例
假设我们的目标k是4，绿色框内的每一个叶子节点都不能满足4，只能加到父节点，但是这四个点都加入父节点以后，紫色框内节点总数就超过4，这说明整棵数是不能分成N/4个联通块的
代码展示
#include<iostream>#include<algorithm>#include<cstring>#include<vector>usingnamespacestd;constintN=101000;intT,n,k;vector<int>branch[N];intdfs(intu,intlast){intans=1;//本身就是一个节点for(inti=0;i<branch[u].size();i++){intnext=branch[u][i];if(next==last)continue;intcnt=dfs(next,u);//看看叶子节点的总节点数if(cnt==-1)return-1;if(cnt==k)cnt=0;ans+=cnt;if(ans>k)return-1;}returnans;}intmain(){cin>>T;while(T--){cin>>n>>k;for(inti=1;i<=n;i++)branch[i].clear();//多测，每组要清理数据intx,y;for(inti=1;i<n;i++){cin>>x>>y;branch[x].push_back(y);branch[y].push_back(x);}intcnt=dfs(1,1);if(cnt==k)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return0;}细节讲解
注意多测要清理之前的数据，dfs中for循环内的几个if语句的关系是环环相扣的，要仔细思考
AI详细注释代码
#include<iostream>#include<algorithm>#include<cstring>#include<vector>usingnamespacestd;constintN=101000;intT,n,k;// T:测试用例数 n:节点数 k:目标分组大小vector<int>branch[N];// 邻接表存储树的边（branch[u]存u的所有邻接节点）// 递归DFS：计算以u为根的子树可分组的节点数（last是父节点，避免回走）intdfs(intu,intlast){intans=1;// 初始：当前节点自身算1个// 遍历u的所有邻接节点for(inti=0;i<branch[u].size();i++){intnext=branch[u][i];if(next==last)continue;// 跳过父节点，避免重复遍历intcnt=dfs(next,u);// 递归计算子节点next的子树节点数if(cnt==-1)return-1;// 子树不满足条件，直接返回-1if(cnt==k)cnt=0;// 子树节点数刚好凑够k，分组后清零ans+=cnt;// 累加当前子树的有效节点数if(ans>k)return-1;// 节点数超过k，无法分组，返回-1}returnans;// 返回当前子树累计的节点数}intmain(){cin>>T;while(T--){cin>>n>>k;// 多组测试用例，清空邻接表for(inti=1;i<=n;i++)branch[i].clear();// 输入n-1条树的边，构建邻接表intx,y;for(inti=1;i<n;i++){cin>>x>>y;branch[x].push_back(y);branch[y].push_back(x);}// 从根节点1开始DFS（父节点设为1，避免回走）intcnt=dfs(1,1);// 最终累计节点数等于k则符合条件，否则不符合if(cnt==k)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return0;}第二篇题解
题目描述
- P1144最短路计数
P1144 最短路计数
题目描述
给出一个N NN个顶点M MM条边的无向无权图，顶点编号为1 ∼ N 1\sim N1∼N。问从顶点1 11开始，到其他每个点的最短路有几条。
输入格式
第一行包含2 22个正整数N , M N,MN,M，为图的顶点数与边数。
接下来M MM行，每行2 22个正整数x , y x,yx,y，表示有一条连接顶点x xx和顶点y yy的边，请注意可能有自环与重边。
输出格式
共N NN行，每行一个非负整数，第i ii行输出从顶点1 11到顶点i ii有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点i ii则输出0 00。
输入输出样例 #1
输入 #1
5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5输出 #1
1 1 1 2 4说明/提示
1 11到5 55的最短路有4 44条，分别为2 22条1 → 2 → 4 → 5 1\to 2\to 4\to 51→2→4→5和2 22条1 → 3 → 4 → 5 1\to 3\to 4\to 51→3→4→5（由于4 → 5 4\to 54→5的边有2 22条）。
对于20 % 20\%20%的数据，1 ≤ N ≤ 100 1\le N \le 1001≤N≤100；
对于60 % 60\%60%的数据，1 ≤ N ≤ 1 0 3 1\le N \le 10^31≤N≤103；
对于100 % 100\%100%的数据，1 ≤ N ≤ 1 0 6 1\le N\le10^61≤N≤106，1 ≤ M ≤ 2 × 1 0 6 1\le M\le 2\times 10^61≤M≤2×106。
思路分析
最短路问题采用bfs，注意到题目中有重边和自环，自环不用读入，因为你如果已经走到某个点了，再通过自环走一次，只会增加距离肯定不是最短路，由于统计的是不同的路径，所以重边是需要读入的。通过bfs扩展到的点，此时到达该点的路径一定是最短的，又因为我们初始化的距离为正无穷，所以第一次达到以后就会重新更新距离，这里是继承上一个路径数量，跟dijkstra类似，标记为true以后表明到这个点的最短距离已经找到，(虽然这里是为了不走回头路)，而之后再次到达该点且距离跟之前相同的话，需要加上上一个路径的数量
代码展示
#include<iostream>#include<algorithm>#include<cstring>#include<vector>#include<queue>usingnamespacestd;constintN=1e6+10,mod=100003;intn,m;boolst[N];//标记已经走过的点intdist[N],path[N];vector<int>branch[N];voidbfs(){queue<int>q;q.push(1);st[1]=true;dist[1]=0;path[1]=1;while(!q.empty()){intt=q.front();q.pop();for(inti=0;i<branch[t].size();i++){intv=branch[t][i];if(dist[t]+1<dist[v]){dist[v]=dist[t]+1;path[v]=path[t];if(!st[v]){st[v]=true;q.push(v);}}elseif(dist[t]+1==dist[v]){path[v]=(path[v]+path[t])%mod;}elsecontinue;}}}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;while(m--){intx,y;cin>>x>>y;if(x==y)continue;branch[x].push_back(y);branch[y].push_back(x);}memset(dist,0x3f,sizeofdist);bfs();for(inti=1;i<=n;i++)cout<<path[i]<<endl;return0;}细节讲解
距离刚开始要初始化为正无穷
AI详细注释代码
#include<iostream>#include<algorithm>#include<cstring>#include<vector>#include<queue>usingnamespacestd;constintN=1e6+10,mod=100003;// N:节点最大数量 mod:路径数取模值intn,m;// n:节点数 m:边数boolst[N];// 标记节点是否入过队列intdist[N];// 存储节点到起点1的最短距离intpath[N];// 存储节点到起点1的最短路径数量vector<int>branch[N];// 邻接表存储图的边// BFS求解最短距离和最短路径数voidbfs(){queue<int>q;q.push(1);// 起点1入队st[1]=true;// 标记起点已入队dist[1]=0;// 起点到自身距离为0path[1]=1;// 起点到自身路径数为1while(!q.empty()){intt=q.front();// 取出队头节点q.pop();// 遍历当前节点的所有邻接节点for(inti=0;i<branch[t].size();i++){intv=branch[t][i];// 邻接节点v// 情况1：找到更短的路径if(dist[t]+1<dist[v]){dist[v]=dist[t]+1;// 更新最短距离path[v]=path[t];// 更新路径数（继承父节点）if(!st[v]){// 未入队则标记并入队st[v]=true;q.push(v);}}// 情况2：找到等长的最短路径elseif(dist[t]+1==dist[v]){path[v]=(path[v]+path[t])%mod;// 累加路径数并取模}// 情况3：路径更长，直接跳过elsecontinue;}}}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);// 加速输入输出cin>>n>>m;// 输入m条边，构建无向图邻接表while(m--){intx,y;cin>>x>>y;if(x==y)continue;// 跳过自环边branch[x].push_back(y);branch[y].push_back(x);}memset(dist,0x3f,sizeofdist);// 初始化最短距离为无穷大bfs();// 输出每个节点到起点1的最短路径数for(inti=1;i<=n;i++)cout<<path[i]<<endl;return0;}
