网站开发 兼容模式杭州自助建站网站

网站开发 兼容模式,杭州自助建站网站,绝味鸭脖网站建设规划书,淘宝里面的网站怎么做的第一篇题解 蒟蒻的第四篇题解希望大家支持 题目描述 P3915树的分解 P3915 树的分解 题目描述 给出 NNN 个点的树和 KKK#xff0c;问能否把树划分成 NK\frac{N}{K}KN​ 个连通块#xff0c;且每个连通块的点数都是 KKK。 输入格式 第一行#xff0c;一个整数 TTT问能否把树划分成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输入 #12 4 2 1 2 2 3 3 4 4 2 1 2 1 3 1 4输出 #1YES 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≤101 ≤ N , K ≤ 1 0 5 1 \le N ,K \le 10^51≤N,K≤105。思路分析这是一道有关于树的遍历的题目和树相关的题目我们一般采用递归实现。在树当中联通块的意思其实就是包括某一个根节点和其所有子节点的一棵子树这题我们就是要将一整棵树一片片地分解开来以某一个节点为根节点进行分析会遇到一下这三种情况1.以该节点为根节点的子树所包括的总节点数小于k2.以该节点为根节点的子树所包括的节点总数等于k3.以该节点为根节点的总结点数大于k接下来我们分别分析这三种情况该如何处理1.总节点数不足k个那么就把这个部分子树并到该根节点的父节点上返回总节点数2.总节点数刚好为k那么这个部分作为一个连通块直接划掉即可返回03.总节点数大于k说明这个一整棵子树无法分成N/K个联通块返回-1即输出一个标记失败情况的数字可能出现的疑惑不知道有同学是否会这样想以该节点为根节点的总节点个数大于k为什么就能判断整棵数不能分成N/K个联通块呢为什么不能把部分节点分给其他子树呢有这个疑惑的同学认真思考了这个问题现在做出解答。因为我们看问题的方式太片面了我们想一想为什么这个以这个节点为根节点的总节点数会大于k呢那当然是因为该节点的叶子节点返回了过多的点这看上去是一句废话但要好好理解一个通俗的解释方式该节点的叶子节点解决不了自己的问题就去向该节点寻求帮助但是寻求帮助以后该节点就无法解决自身的问题因为总节点数超过k对于叶子节点来说他自己解决不了问题数量不足k个向上寻求帮助也解决不了问题那么这个节点的问题无论如何也解决不了即无论如何也不能凑出k个节点给出一个案例假设我们的目标k是4绿色框内的每一个叶子节点都不能满足4只能加到父节点但是这四个点都加入父节点以后紫色框内节点总数就超过4这说明整棵数是不能分成N/4个联通块的代码展示#includeiostream#includealgorithm#includecstring#includevectorusingnamespacestd;constintN101000;intT,n,k;vectorintbranch[N];intdfs(intu,intlast){intans1;//本身就是一个节点for(inti0;ibranch[u].size();i){intnextbranch[u][i];if(nextlast)continue;intcntdfs(next,u);//看看叶子节点的总节点数if(cnt-1)return-1;if(cntk)cnt0;anscnt;if(ansk)return-1;}returnans;}intmain(){cinT;while(T--){cinnk;for(inti1;in;i)branch[i].clear();//多测每组要清理数据intx,y;for(inti1;in;i){cinxy;branch[x].push_back(y);branch[y].push_back(x);}intcntdfs(1,1);if(cntk)coutYESendl;elsecoutNOendl;}return0;}细节讲解注意多测要清理之前的数据dfs中for循环内的几个if语句的关系是环环相扣的要仔细思考AI详细注释代码#includeiostream#includealgorithm#includecstring#includevectorusingnamespacestd;constintN101000;intT,n,k;// T:测试用例数 n:节点数 k:目标分组大小vectorintbranch[N];// 邻接表存储树的边branch[u]存u的所有邻接节点// 递归DFS计算以u为根的子树可分组的节点数last是父节点避免回走intdfs(intu,intlast){intans1;// 初始当前节点自身算1个// 遍历u的所有邻接节点for(inti0;ibranch[u].size();i){intnextbranch[u][i];if(nextlast)continue;// 跳过父节点避免重复遍历intcntdfs(next,u);// 递归计算子节点next的子树节点数if(cnt-1)return-1;// 子树不满足条件直接返回-1if(cntk)cnt0;// 子树节点数刚好凑够k分组后清零anscnt;// 累加当前子树的有效节点数if(ansk)return-1;// 节点数超过k无法分组返回-1}returnans;// 返回当前子树累计的节点数}intmain(){cinT;while(T--){cinnk;// 多组测试用例清空邻接表for(inti1;in;i)branch[i].clear();// 输入n-1条树的边构建邻接表intx,y;for(inti1;in;i){cinxy;branch[x].push_back(y);branch[y].push_back(x);}// 从根节点1开始DFS父节点设为1避免回走intcntdfs(1,1);// 最终累计节点数等于k则符合条件否则不符合if(cntk)coutYESendl;elsecoutNOendl;}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输入 #15 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5输出 #11 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≤1061 ≤ M ≤ 2 × 1 0 6 1\le M\le 2\times 10^61≤M≤2×106。思路分析最短路问题采用bfs注意到题目中有重边和自环自环不用读入因为你如果已经走到某个点了再通过自环走一次只会增加距离肯定不是最短路由于统计的是不同的路径所以重边是需要读入的。通过bfs扩展到的点此时到达该点的路径一定是最短的又因为我们初始化的距离为正无穷所以第一次达到以后就会重新更新距离这里是继承上一个路径数量跟dijkstra类似标记为true以后表明到这个点的最短距离已经找到(虽然这里是为了不走回头路)而之后再次到达该点且距离跟之前相同的话需要加上上一个路径的数量代码展示#includeiostream#includealgorithm#includecstring#includevector#includequeueusingnamespacestd;constintN1e610,mod100003;intn,m;boolst[N];//标记已经走过的点intdist[N],path[N];vectorintbranch[N];voidbfs(){queueintq;q.push(1);st[1]true;dist[1]0;path[1]1;while(!q.empty()){inttq.front();q.pop();for(inti0;ibranch[t].size();i){intvbranch[t][i];if(dist[t]1dist[v]){dist[v]dist[t]1;path[v]path[t];if(!st[v]){st[v]true;q.push(v);}}elseif(dist[t]1dist[v]){path[v](path[v]path[t])%mod;}elsecontinue;}}}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnm;while(m--){intx,y;cinxy;if(xy)continue;branch[x].push_back(y);branch[y].push_back(x);}memset(dist,0x3f,sizeofdist);bfs();for(inti1;in;i)coutpath[i]endl;return0;}细节讲解距离刚开始要初始化为正无穷AI详细注释代码#includeiostream#includealgorithm#includecstring#includevector#includequeueusingnamespacestd;constintN1e610,mod100003;// N:节点最大数量 mod:路径数取模值intn,m;// n:节点数 m:边数boolst[N];// 标记节点是否入过队列intdist[N];// 存储节点到起点1的最短距离intpath[N];// 存储节点到起点1的最短路径数量vectorintbranch[N];// 邻接表存储图的边// BFS求解最短距离和最短路径数voidbfs(){queueintq;q.push(1);// 起点1入队st[1]true;// 标记起点已入队dist[1]0;// 起点到自身距离为0path[1]1;// 起点到自身路径数为1while(!q.empty()){inttq.front();// 取出队头节点q.pop();// 遍历当前节点的所有邻接节点for(inti0;ibranch[t].size();i){intvbranch[t][i];// 邻接节点v// 情况1找到更短的路径if(dist[t]1dist[v]){dist[v]dist[t]1;// 更新最短距离path[v]path[t];// 更新路径数继承父节点if(!st[v]){// 未入队则标记并入队st[v]true;q.push(v);}}// 情况2找到等长的最短路径elseif(dist[t]1dist[v]){path[v](path[v]path[t])%mod;// 累加路径数并取模}// 情况3路径更长直接跳过elsecontinue;}}}intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);// 加速输入输出cinnm;// 输入m条边构建无向图邻接表while(m--){intx,y;cinxy;if(xy)continue;// 跳过自环边branch[x].push_back(y);branch[y].push_back(x);}memset(dist,0x3f,sizeofdist);// 初始化最短距离为无穷大bfs();// 输出每个节点到起点1的最短路径数for(inti1;in;i)coutpath[i]endl;return0;}