-
hdoj 4738 tarjan求无向图的桥
2015-08-10 11:56:33桥的概念:无向连通图中,删掉某条边可以使原图不连通,那么该边就是无向图的桥。 tarjan算法求桥的思想简单说一下:以任意一点开始建立搜索树,记录每个点的搜索深度dep和非父子边能到达的最早节点深题意:有n个点m条边,问如果删掉一条边使图不连通,问最少需要多少兵力。每条边都有驻守的士兵,如果想删掉这条边至少要派相同人数的士兵。
思路:就是一个连通图求最小权的桥的问题。
桥的概念:无向连通图中,删掉某条边可以使原图不连通,那么该边就是无向图的桥。
tarjan算法求桥的思想简单说一下:以任意一点开始建立搜索树,记录每个点的搜索深度dep和非父子边能到达的最早节点深度low,就是说这条路上可能有一个环,这个环里的最小的搜索深度就是low,如果没有环,那么dep=low(父子边成环)。
解题思路:这个题比较裸但是坑点比较多,首先图可能是不连通的,要先判断一下,我是用的并查集,如果本身就不连通,输出0即可;如果某条边守卫为0,也应该派1个被炸药的过去。。。
写了个模板留着以后用。
PS:这个题的内存限制开的有点小,应该说网上大部分题解的代码都过不了,因为边最多有100w条,记双向边又要200w,一个结构体或类里存4~5个int,能过才有鬼。
之所以没有mle是因为hdoj的判题机制貌似是看程序运行实际用到了多少内存,而不是声明了多少内存。
(我也没别的意思就是吐槽一下因为我太蠢写了个没用的memset结果mle了好久。。。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int M = 1005; struct Edge{ int to, next, id, val; Edge(){} Edge(int a, int b, int c, int d): to(a), next(b), id(c), val(d){} }edge[M * M * 2]; int _next[M], edgeCnt, dep[M], low[M], nowdep, bridge[M * M * 2]; bool isBridge[M * M]; void addEdge(int from, int to, int val, int id){ edge[++edgeCnt] = Edge(to, _next[from], id, val); _next[from] = edgeCnt; edge[++edgeCnt] = Edge(from, _next[to], id, val); _next[to] = edgeCnt; } void tarjanInit(){ memset(dep, 0, sizeof dep); memset(low, 0, sizeof low); memset(isBridge, 0, sizeof isBridge); nowdep = 0; } void tarjan(int from, int id) { dep[from] = low[from] = ++nowdep; for(int i = _next[from]; i; i = edge[i].next){ if(edge[i].id == id) continue; int to = edge[i].to; if(!dep[to]){ tarjan(to, edge[i].id); low[from] = min(low[from], low[to]); if(dep[from] < low[to]) isBridge[i] = true; } else low[from] = min(low[from], dep[to]); } } int tarjanGetBridge() { tarjanInit(); tarjan(1, 0); int cnt = 0; for(int i = 1; i <= edgeCnt; i++) if(isBridge[i]) bridge[cnt++] = i; return cnt; } / int father[M]; void init() { for(int i = 1; i <= M; i++) father[i] = i; // memset(edge, 0, sizeof edge);(╯‵□′)╯︵┴─┴ memset(_next, 0, sizeof _next); edgeCnt = 0; } int getfather(int a) { return a == father[a] ? a : father[a] = getfather(father[a]); } int unit(int a, int b){ int t1 = getfather(a), t2 = getfather(b); father[t1] = min(t1, t2); father[t2] = min(t1, t2); } main() { int n, m; while(~scanf("%d %d", &n, &m)){ if(n == 0 && m == 0) break; init(); for(int i = 1; i <= m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); addEdge(a, b, c, i); unit(a, b); } bool flag = true; for(int i = 1; i <= n; i++) if(getfather(i) != father[1]) flag = false; if(!flag){ puts("0"); continue; } int cnt = tarjanGetBridge(); int ans = 0x7fffffff; for(int i = 0; i < cnt; i++) { ans = min(ans, edge[bridge[i]].val); } if(ans == 0) puts("1"); else if(ans == 0x7fffffff) puts("-1"); else printf("%d\n", ans); } }
-
【强连通】洛谷 P3388 (这个题怕不是洛谷最简单的题……)
2019-07-31 23:05:13给出一个nn个点,mm条边的无向图,求图的割点。 输入格式 第一行输入n,mn,m 下面mm行每行输入x,yx,y表示xx到yy有一条边 输出格式 第一行输出割点个数 第二行按照节点编号从小到大输出节点,用空格隔开 输入...题目背景
割点
题目描述
给出一个nn个点,mm条边的无向图,求图的割点。
输入格式
第一行输入n,mn,m
下面mm行每行输入x,yx,y表示xx到yy有一条边
输出格式
第一行输出割点个数
第二行按照节点编号从小到大输出节点,用空格隔开
输入输出样例
输入 #1
6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6
输出 #1
1 5
说明/提示
对于全部数据,n \le 20000n≤20000,m \le 100000m≤100000
点的编号均大于00小于等于nn。
tarjan图不一定联通。
套用Tarjan模板:
#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<stack> #include<queue> #include<map> #include<set> #include<algorithm> using namespace std; #define lowbit(x) (x&-x) #define mem(a,b) memset(a,b,sizeof(a)) #define eps 1e-9 #define INF 999999 #define MAXN 20005 //struct edge{ // int to; // //int val; //}; //int next[MAXN]; vector<int> G[MAXN]; int dfn[MAXN],low[MAXN]; bool instack[MAXN]; set<int> ans; //存储割点 //stack<int> s; int timing; //时间戳 int color[MAXN]; //代表当前结点所属第几个scc int colorcnt[MAXN]; //代表第某个scc有几个结点 int cnt; //scc个数 int V,E; void init() { for(int i=0;i<=V;i++) G[i].clear(); ans.clear(); mem(dfn,0); mem(color,0); mem(colorcnt,0); mem(instack,false); mem(low,0); timing=cnt=0; } //割点 void tarjan(int u,int rt) { ++timing; low[u]=dfn[u]=timing; int child=0; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(dfn[v]==0) { child++; tarjan(v,rt); low[u]=min(low[u],low[v]); if(u!=rt && low[v]>=dfn[u]){ ans.insert(u); } } low[u]=min(low[u],dfn[v]); } if(child>=2&&u==rt){ ans.insert(u); } } int main() { ios::sync_with_stdio(false); cin >> V >> E; int x,y; for(int i=1;i<=E;i++) { cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } for(int i=1;i<=V;i++){ if(dfn[i]==0) tarjan(i,i); } cout << ans.size() << endl; set<int>::iterator ite; for(ite=ans.begin();ite!=ans.end();ite++) cout << *ite << " "; cout << endl; return 0; }
-
图论 —— 二分图 —— 二分图判定
2019-02-20 22:45:48二分图的判定问题比较少见,简单来说,就是对于给定的图,判断...无向图 G 为二分图的充分必要条件:G 至少有两个顶点,且其所有回路的长度均为偶数。 int n;//节点数 vector<int> G[N];//G[i]表示i...二分图的判定问题比较少见,简单来说,就是对于给定的图,判断图是否为二分图。
可以把每个节点着以黑色和白色之一,使得每条边的两个端点颜色不同,不难发现,对于一个当且仅当每个连通分量都是二分图,因此我们只考虑无向连通图。
无向图 G 为二分图的充分必要条件:G 至少有两个顶点,且其所有回路的长度均为偶数。
int n;//节点数 vector<int> G[N];//G[i]表示i节点邻接的点 int color[N];//color[i]=0,1,2 表i节点不涂颜色、涂白色、涂黑色 bool bipartite(int u)//判断无向图是否可二分 { for(int i=0;i<G[u].size();i++)//枚举结点 { int v=G[u][i];//相邻节点 if(color[v]==color[u])//若两结点颜色相同,无法二分 return false; if(!color[v])//若结点没涂颜色 { color[v]=3-color[u];//改变结点颜色,使v的颜色与u的颜色对立 if(!bipartite(v))//若点v不满足二分图话,则无法二分 return false; } } return true; }
-
LeetCode310最小高度树-图-拓扑排序理解
2021-01-30 23:27:11树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含n个节点的数,标记为0到n - 1 。给定数字n和一个有 n - 1 条无向边的 edges列表(每一个...题目描述
树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。
给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表(每一个边都是一对标签),其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时,设结果树的高度为 h 。在所有可能的树中,具有最小高度的树(即,min(h))被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
提示:
1 <= n <= 2 * 104
edges.length == n - 1
0 <= ai, bi < n
ai != bi
所有 (ai, bi) 互不相同
给定的输入 保证 是一棵树,并且 不会有重复的边拓扑排序
连续两天做了3道拓扑排序的题目,有一些心得
拓扑排序--原型
拓扑排序--原型--直接实现:
它是一个 DAG 图,那么如何写出它的拓扑排序呢?这里说一种比较常用的方法:
实现步骤:
STEP1 从 DAG 图中选择一个 没有前驱(即入度为0)的顶点并输出。
STEP2 从图中删除该顶点和所有以它为起点的有向边。
STEP3 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
复杂度分析:
直接实现的话,每删除一个结点循环一次(共n次),每次循环都需要遍历整个图寻找无前驱结点,遍历图的复杂度为O(n^2),所以总复杂度为O(n^3)
拓扑排序--原型--栈实现:
心得: 我发现,算法的逻辑可以用一些简单的逻辑来等效,从而降低复杂度
等效过程:
STEP1 从 DAG 图中选择一个 没有前驱(即入度为0)的顶点并输出。
STEP1 等效为--> 扫描顶点表,将没有前驱(即入度为0)的顶点压栈;
STEP2 从图中删除该顶点和所有以它为起点的有向边。
STEP2.1 "删除该顶点" 等效为-->在 "判断结点是否被访问的数组"(boolean[] isTraveled) 中 ,标记为已访问
STEP2.2 "删除所有以它为起点的有向边" 等效为-->在 "入边统计"数组"(int[] nodeInEdgeCount) 中 ,将以顶点index为起点 的 各个邻接点 的 入度 减1;
等效后,算法所需要使用的所有辅助数据结构如下
//辅助数据结构 int[][] graph = new int[numCourses][numCourses];//图的邻接矩阵 int[] nodeInEdgeCount = new int[numCourses];//"入边统计"数组 Stack<Integer> zeroInStack = new Stack<>();//入度为0的结点栈 boolean[] isTraveled = new boolean[graph.length];//判断结点是否被访问的数组,被访问记为true int countTravel = 0;//已经被访问的结点个数
实现步骤:
扫描顶点表,将没有前驱(即入度为0)的顶点压栈;
当栈S非空时循环
3.1 退出栈顶元素index;输出栈顶元素index;累加器加1;
3.2 将以顶点index为起点 的 各个邻接点 的 入度 减1; (从图中删除该顶点和所有以它为起点的有向边。)
3.3 将新的入度为0的顶点入栈;
if (count<vertexNum) 输出有回路信息;复杂度分析:
在"直接实现"的基础上省略了 "每次循环都需要遍历整个图寻找无前驱结点" 这个过程 ,复杂度为O(n^2)
拓扑排序--变式(本题)--栈实现
修改的点:
1 本题是无向图,而 拓扑排序--原型 是有向图
2 本题是删除 [边数]为1 的点 ,而不是"入度"为1 的点
3 因为本题可能会有多个"最小高度树根结点"需要输出,所以不能一个个地删除粗结点,
所以需要像 "二叉树层序遍历--带层数计数" 的实现方式一样,一次性删除一整层的所有 [边数]为1 的结点
实现步骤+等效逻辑:
STEP1 初始化"储存只有一条边的结点的栈" 找到[边数]为1的所有结点
STEP2 循环
STEP2.1 一次性把所有队列中[边数]为1的结点出队,
出队的同时 把该[结点]删除,把与该结点有关的[边]删除
STEP2.1.1 把该[结点]删除-->等效为 把 结点i 标记为已访问 isTraveled[i]=true
STEP2.1.2 把与该结点有关的[边]删除-->等效为 把 结点i 相连接的其余所有结点的边数减1 for(){ edgeCount[j]-=1; }STEP2.2 把新的[边数]为1的结点入队
STEP2.2 把新的[边数]为1的结点入队-->等效为 把 edgeCount==1&&isTraveled[]==false 的结点入队STEP2.3 如果剩余未被访问结点数 等于 [边数]为1的结点数,则返回剩余未被访问结点(他们就是最小高度树的树根,可能有很多个)
STEP2.3 -->等效为 返回 当前[边数]为1的结点的list
拓扑排序总结
拓扑排序本质上是针对 "边" 进行的一种操作, 这让我不禁深入思考,还可以有什么别的针对"边"的操作?
一个结点的边有如下性质
1 有几条边
2 出度/入度
3 边的长度
4 边可删除
比如:
1访问结点后删除边 (边条数改变)(入度/出度 改变)
2每轮循环访问"符合边数要求"的结点 (边条数判断)(入度/出度 判断)
几个值得思考的问题
对于 栈/队列 这种辅助数据结构
是出栈访问,还是入栈访问?--以及重复入栈的问题
//入队就标记为已访问(出队时才标记已经访问的话,会导致重复入队),(因为有 1.出队判定为访问 和 2.入队判定为访问 两大流派)后来我总结了这个重复入队的问题根源,那就是"在哪里判断了是否已经入队""就在哪里更新"入队判断符号"",比如在这里进行了if(isTraveled[i]==false)判断,就要在这里更新入队判断符isTraveled[i]=true;
实现代码
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; //编程思维 //线性思维,顺序思维 //让人类理解编程思维(人机工效) //在脑子里想象一张程序框图 class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { //建立辅助数据结构 int[] edgeCount = new int[n];//结点[边数]统计数组 下标为i的格子储存着下标为i的结点的[边数] boolean[] isTraveled = new boolean[n];//结点是否被访问数组 被访问为true int travelCount = 0;//被访问的结点个数计数器 Queue<Integer> oneEdgeQueue = new LinkedList<>();//当前[边数]为1的结点的队列queue List<Integer> oneEdgeList = new LinkedList<>();//当前[边数]为1的结点的list //输入处理 //根据prerequisite和numCourses建立图 boolean[][] graph = new boolean[n][n]; for(int i=0;i<edges.length;i++){ int startNode = edges[i][1]; int endNode = edges[i][0]; graph[endNode][startNode] = true; graph[startNode][endNode] = true; edgeCount[startNode] += 1; edgeCount[endNode] += 1; } //STEP1 初始化"储存只有一条边的结点的栈" 找到[边数]为1的所有结点 int oneEdgeNodeCount_ = 0; for(int i=0;i<n;i++){ int countEdge_temp = 0; for(int j=0;j<n;j++){ if(graph[i][j]==true){ countEdge_temp += 1; } } if(countEdge_temp<=1 && isTraveled[i]==false){//如果[边数]为1 oneEdgeQueue.offer(i); isTraveled[i]=true; travelCount+=1; oneEdgeList.add(i); oneEdgeNodeCount_+=1; } } int noTraveledCount_ = n;//剩余未被访问结点数 if(noTraveledCount_ == oneEdgeNodeCount_){ return oneEdgeList; } //STEP2 循环 while(true){ //STEP2.1 一次性把所有队列中[边数]为1的结点出队, //出队的同时 把该[结点]删除,把与该结点有关的[边]删除 //STEP2.1.1 把该[结点]删除-->等效为 把 结点i 标记为已访问 isTraveled[i]=true //STEP2.1.2 把与该结点有关的[边]删除-->等效为 把 结点i 相连接的其余所有结点的边数减1 for(){ edgeCount[j]-=1; } int nowQueueSize = oneEdgeQueue.size();//需要提前获取队列的大小,否则删除过程中由于队列大小缩小,会出错 for(int i=0;i<nowQueueSize;i++){ int index = oneEdgeQueue.poll(); System.out.println(index); //STEP2.1 出队的同时 把该[结点]删除,把与该结点有关的[边]删除 //STEP2.1.2 把与该结点有关的[边]删除-->等效为 把 结点i 相连接的其余所有结点的边数减1 for(){ edgeCount[j]-=1; } for(int j=0;j<n;j++){ if(graph[index][j]==true){//把 结点i 相连接的其余所有结点的边数减1 edgeCount[j]-=1; } } } //STEP2.2 把新的[边数]为1的结点入队 //STEP2.2 把新的[边数]为1的结点入队-->等效为 把 edgeCount==1&&isTraveled[]==false 的结点入队 int oneEdgeNodeCount = 0; int travelCount_old = travelCount; oneEdgeList = new LinkedList<>();//刷新list "当前[边数]为1的结点的list" for(int i=0;i<edgeCount.length;i++){ if(edgeCount[i]<=1 && isTraveled[i]==false){ oneEdgeQueue.offer(i); isTraveled[i]=true;//入队就标记为已访问(出队时才标记已经访问的话,会导致重复入队),(因为有 1.出队判定为访问 和 2.入队判定为访问 两大流派)后来我总结了这个重复入队的问题根源,那就是"在哪里判断了是否已经入队""就在哪里更新"入队判断符号"",比如在这里进行了if(isTraveled[i]==false)判断,就要在这里更新入队判断符isTraveled[i]=true; travelCount+=1; oneEdgeNodeCount+=1; oneEdgeList.add(i); } } //现在思考在最后的情景 //STEP2.3 如果剩余未被访问结点数 等于 [边数]为1的结点数,则返回剩余未被访问结点(他们就是最小高度树的树根,可能有很多个) //STEP2.3 -->等效为 返回 当前[边数]为1的结点的list int noTraveledCount = n - travelCount_old;//剩余未被访问结点数 if(noTraveledCount == oneEdgeNodeCount){ return oneEdgeList; } //System.out.println("一轮结束"); } } public static void main(String[] args) { Solution s = new Solution(); //int[][] grap = {{3,0},{3,1},{3,2},{3,4},{5,4}};//6 //int[][] grap = {{0,1}};//2 //int[][] grap = {{1,0},{1,2},{1,3}};//4 int[][] grap = {};//1 List<Integer> a = s.findMinHeightTrees(1,grap); System.out.println(a); } }
惨烈的AC结果...至少是自己做的
-
图片有的不显示.br标签和a标签直接显示出来.版本0.1.0. 文本如下
2020-12-04 13:58:15有且仅有一个特定的称为根(root)的结点。 (2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树,并且称为根的... -
数据结构复习笔记六:图
2014-02-28 17:17:554、完全图:n个节点的无向完全图|有向完全图 5、度、出度和入度(顶点数、边数与各顶点的度之间的关系) 6、路径:回路或环|简单路径 7、子图 8、连通图和连通分量 9、强连通图和强连通分量 10、网 11、有 -
bzoj3456城市规划 多项式取模
2017-02-13 15:04:00求出有n个点的有标号简单连通无向图的数目。 题解 什么破玩意,直接输出\(2^{C_n^2}\)走人 我们发现这张图要求连通,而上式肯定不能保证连通。 其实上式表示的是不保证连通的有标号简单无向图。 就差在一个连通上啊... -
离散数学第12章树
2021-01-09 16:56:36结论:树都是简单无向图,连通,无圈,m = n-1 连通无圈 无自环且每对节点之间的基本链唯一 有基本链说明连通,基本链唯一再加上无自环就是无圈 连通,加一边仅会导致有一个圈 如果加一条边会有两个圈,那么去掉... -
数据结构-树的类别
2019-04-17 11:19:41③一棵树有N个节点,那一定有n-1条边 二叉树 含义:含义每个节点只有两个子节点的树,时间复杂度为O(log n) 完全二叉树 含义:二叉树的高度为h时,1~h-1层的节点数达到最大数,第h层从左往右连续缺少节点的二叉树 ... -
LeetCode 310 最小高度树
2021-01-11 17:30:52树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一 棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges ... -
双联通缩点/树上差分(石油大学组队赛I: One-Way Conveyors)
2020-09-06 19:44:43题意:给你一个n点m边无向图。你需要给每一个边定向,然后必须让所给的k对点是可达的。 题解: 首先明确一点,我们通过边定向,是可以将一个无向图边双连通块构成一个强连通块的。构造方法也很简单,直接在块内dfs,... -
leetcode 310. 最小高度树
2021-01-15 21:59:26树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表... -
310. 最小高度树
2020-12-28 22:15:59树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表... -
310 最小高度树
2020-11-24 14:28:40树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表... -
LeetCode 310. 最小高度树--树的直径
2020-11-19 19:51:23树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表... -
【JZOJ1914】【BZOJ2125】最短路
2019-12-23 22:10:44给一个N个点M条边的连通无向图,满足每条边最多属于一个环,有Q组询问,每次询问两点之间的最短路径。 analysis 建出圆方树后,可以知道仙人掌上每一个方点连着的边双其实就是一个简单环 tarjantarjantarjan缩... -
入门学习Linux常用必会60个命令实例详解doc/txt
2011-06-09 00:08:45hda1中的“1”代表hda的第一个硬盘分区 (partition),hda2代表hda的第二主分区,第一个逻辑分区从hda5开始,依此类推。此外,可以直接检查 /var/log/messages文件,在该文件中可以找到计算机开机后系统已辨认出来的... -
【例题收藏】◇例题·II◇ Berland and the Shortest Paths
2018-07-19 22:46:00给定一个n个点、m条边的无向图。保证图是连通的,且m≥n-1。 以首都(1节点)为根节点生成最小树。树的值定义为每个节点的深度和(根节点深度0)。举个例子: 而我们知道,可能有多种情况使树的权值最小,题目给... -
PAT 1013 C++ 版
2019-02-12 20:42:49给出一个查询数据,判断如果从图中去掉这个顶点,以及这个顶点外的所有边时,求:还需要几条边使得这个无向图连通? 如果不需要任何边,则输出0;如果有的话,则输出需要的边数n。 2.分析 题目比较简单。 涉及到无向... -
bzoj3124[Sdoi2013]直径(树dp)
2017-10-31 18:50:32如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b) 表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:一... -
[bzoj3124][乱搞]直径
2018-04-21 15:22:29如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b) 表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:... -
[洛谷P3304] [SDOI2013]直径
2019-09-23 23:24:50如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:一棵树上... -
[SDOI2013]直径(树的直径)
2019-10-01 04:42:14如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:一棵树上... -
【BZOJ3124】[Sdoi2013]直径 树形DP(不用结论)
2017-09-17 18:49:00如果一棵树有N个节点,可以证明其有且仅有N-1条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离... -
[SDOI2013] 直径
2018-08-22 10:35:00如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:一棵树上... -
[BZOJ3124]直径
2018-07-31 21:06:00如果一棵树有N个节点,可以证明其有且仅有N-1条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。直径:一棵树上,... -
【JZOJ3213】【SDOI2013】直径
2017-02-14 17:03:00如果一棵树有N个节点,可以证明其有且仅有 N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点 a 和点 b 的路径上各边长度之和。称 dis(a,b)为 a、b 两个节点间的距离。 直径...
-
java 定时任务 实例_Java Timer 定时器的使用执行任务实例教程
-
MHA 高可用 MySQL 架构与 Altas 读写分离
-
家庭收支统计表V4.11.xlsx.7z
-
做网站用java 还是php_做网站用java还是php
-
MySQL 四类管理日志(详解及高阶配置)
-
利用JavaMail for Android和MailSender实现发送邮件
-
Python大作业-学生成绩管理系统
-
百度云推送java服务端_百度云推送java服务器怎么弄
-
Bootstrap(V3.3.7).zip
-
java 安全配置_java – Spring启动安全配置 – 必须指定authenticationManager
-
java 安卓 接口怎么写_Android开发者怎么能不会写后台接口呢?
-
wgcloud-v3.3.0运维监控系统(linux版本)
-
【Python-随到随学】 FLask第一周
-
使用vue搭建微信H5公众号项目
-
【布道者】Linux极速入门
-
7. ASCII码破密.cpp
-
深入嵌入式Java虚拟机_深入嵌入式Java虚拟机
-
java 字节码对象_java字节码对象,获取字节码的三种方式是什么?
-
java执行sed命令_sed命令无法从Java运行
-
腾讯研究院-未来经济白皮书2021:数实共生.zip