2020-2021:teams:hotpot:diameterandweight
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:diameterandweight [2020/06/11 12:18] misakatao 更新 |
2020-2021:teams:hotpot:diameterandweight [2020/06/11 12:35] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| ======树的直径求解====== | ======树的直径求解====== | ||
| - | 第一种方法是利用性质2，首先从任意一个点开始bfs，找到一个离这个点最远的点，这样就找到了直径的一端，然后我们从这个点再开始bfs就可以同时找出直径的长度和直径的两端。但这种方法的缺点是不能处理有负权的情况。代码实现十分简单，这里就不给出了。 | + | 第一种方法是利用性质2，首先从任意一个点开始bfs，找到一个离这个点最远的点，这样就找到了直径的一端，然后我们从这个点再开始bfs就可以同时找出直径的长度和直径的两端。但这种方法的缺点是不能处理有负权的情况。代码实现十分简单，这里就不给出了。时间复杂度$O(n)$。 |
| 第二种方法是树形DP，令$f_1[i]$表示节点$i$到它叶子节点路径长度的最大值，$f_2[i]$表示节点$i$到它叶子节点路径长度的次大值，我们只需要按照正常记录最大值和次大值的方法更新，最后的答案即为$max\{ f_1[i] + f_2[i] \}$，这一方法可以处理负权，但是很难确定直径的两端是哪两个节点。代码实现可以看[[https://blog.csdn.net/forever_dreams/article/details/81051578|这篇博客]] | 第二种方法是树形DP，令$f_1[i]$表示节点$i$到它叶子节点路径长度的最大值，$f_2[i]$表示节点$i$到它叶子节点路径长度的次大值，我们只需要按照正常记录最大值和次大值的方法更新，最后的答案即为$max\{ f_1[i] + f_2[i] \}$，这一方法可以处理负权，但是很难确定直径的两端是哪两个节点。代码实现可以看[[https://blog.csdn.net/forever_dreams/article/details/81051578|这篇博客]] | ||
| 行 44: | 行 44: | ||
| - | =====例题2—— | + | =====例题2——Adjoin the Networks===== |
| + | |||
| + | [[https://nanti.jisuanke.com/t/A1385|传送门]] | ||
| + | |||
| + | ====题目大意==== | ||
| + | |||
| + | 给出一个森林，求一种链接方式，将森林连成一棵树，并让树的直径最短。边权均为1。 | ||
| + | |||
| + | ====解题思路==== | ||
| + | |||
| + | 应用性质3，由于边权均为1，我们假设两棵树的直径长度分别为 $a,b$且 $a \le b$ ,则： | ||
| + | |||
| + | 若$ b \ge a+3 $,则新树的直径长度仍为 $ b $, | ||
| + | |||
| + | 若$ b == a+2 $,当 $b$ 为奇数时，新树直径为 $b+1$, 当 $b$ 为偶数时，直径长度不改变。 | ||
| + | |||
| + | 若 $ b == a+1 $, 新树直径为 $ b+1 $。 | ||
| + | |||
| + | 经过以上分析，采取贪心的思想，我们只需要考虑前三大的直径就能保证直径不再扩大。其它的树相连后直径不会超过前三形成的直径。 | ||
| + | |||
| + | ====代码实现==== | ||
| + | |||
| + | <del>直接把林佬的代码偷过来</del> | ||
| + | |||
| + | <code cpp> | ||
| + | #include<algorithm> | ||
| + | #include<stack> | ||
| + | #include<ctime> | ||
| + | #include<cstring> | ||
| + | #include<cmath> | ||
| + | #include<iostream> | ||
| + | #include<iomanip> | ||
| + | #include<cstdio> | ||
| + | #include<queue> | ||
| + | using namespace std; | ||
| + | inline int read(){ | ||
| + | int num=0,f=1;char x=getchar(); | ||
| + | while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();} | ||
| + | while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();} | ||
| + | return num*f; | ||
| + | } | ||
| + | const int maxn=10005; | ||
| + | vector<int> e[maxn]; | ||
| + | int n,m; | ||
| + | int vst[maxn],dis[maxn]; | ||
| + | queue<int> Q; | ||
| + | int solve(int s){ | ||
| + | vst[s]=0;Q.push(s); | ||
| + | int t=s,tmp=0; | ||
| + | while(Q.size()){ | ||
| + | int x=Q.front();Q.pop(); | ||
| + | for(auto y:e[x]){ | ||
| + | if(vst[x]+1>vst[y]){ | ||
| + | vst[y]=vst[x]+1; | ||
| + | Q.push(y); | ||
| + | if(vst[y]>tmp)tmp=vst[y],t=y; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | dis[t]=0;Q.push(t);tmp=0; | ||
| + | while(Q.size()){ | ||
| + | int x=Q.front();Q.pop(); | ||
| + | for(auto y:e[x]){ | ||
| + | if(dis[x]+1>dis[y]){ | ||
| + | dis[y]=dis[x]+1; | ||
| + | Q.push(y); | ||
| + | tmp=max(tmp,dis[y]); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | printf("%d\n", tmp); | ||
| + | return tmp; | ||
| + | } | ||
| + | int ans=0; | ||
| + | void get_ans(int x){ | ||
| + | if(ans != 0) | ||
| + | ans=max(ans,(ans+1)/2+(x+1)/2+1); | ||
| + | ans=max(ans,x); | ||
| + | } | ||
| + | int main(){ | ||
| + | n=read();m=read(); | ||
| + | for(int i=1,x,y;i<=m;++i){ | ||
| + | x=read()+1;y=read()+1; | ||
| + | e[x].push_back(y); | ||
| + | e[y].push_back(x); | ||
| + | } | ||
| + | for(int i=1;i<=n;++i)vst[i]=dis[i]=-1; | ||
| + | for(int i=1,t;i<=n;++i){ | ||
| + | if(vst[i] == -1) | ||
| + | { | ||
| + | t=solve(i); | ||
| + | get_ans(t); | ||
| + | } | ||
| + | } | ||
| + | printf("%d\n",ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | ======树的重心及其性质====== | ||
| + | |||
| + | 树的重心的定义为，树的所有点中，以某一个点为根，最大的子树大小最小的点。 | ||
| + | |||
| + | 树的重心有这些性质： | ||
| + | |||
| + | 1.树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个距离和，他们的距离和一样。 | ||
| + | |||
| + | 2.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。 | ||
| + | |||
| + | 3.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。 | ||
| + | |||
| + | 4.一棵树最多有两个重心，且相邻。 | ||
| + | |||
| + | 树的重心一般在点分治等算法中应用。 | ||
| + | |||
| + | ======树的重心的求解====== | ||
| + | |||
| + | 树的重心可以用树形DP的方式求解，以任意一个点为根，每到一个点记录这个点的每颗子树的大小，并把除了以这个点为根的子树意外的部分也当作一个子树，找到其中大小最大的并记录，整体找到记录值最小的点就是重心，时间复杂度为$O(n)$。递归部分代码如下 | ||
| + | |||
| + | <code cpp> | ||
| + | inline void find(int x, int fa, int siz) | ||
| + | { | ||
| + | size[x] = 1; | ||
| + | int sons = 0; | ||
| + | for(int i = F[x];i != -1;i = nex[i]) | ||
| + | { | ||
| + | int t = v[i]; | ||
| + | if(t == fa) | ||
| + | continue; | ||
| + | find(t, x, siz); | ||
| + | if(size[t] > sons) | ||
| + | sons = size[t]; | ||
| + | size[x] += size[t]; | ||
| + | } | ||
| + | if(siz - size[x] > sons) | ||
| + | sons = siz - size[x]; | ||
| + | if(num > sons) | ||
| + | num = sons, g = x; | ||
| + | } | ||
| + | </code> | ||
2020-2021/teams/hotpot/diameterandweight.1591849122.txt.gz · 最后更改: 2020/06/11 12:18 由 misakatao
