P3304 [SDOI2013]直径 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 还没有评论
作者: 1h4x928_ 更新时间: 2019-07-27 19:16  在Ta的博客查看 举报    0  
/*
直径: 正权求法两次dfs:
1. 任意选一个点做为根,找最长的一个点p1
2. 用p1做根,找最长一个点q,  p1->q就是一条直径

2.1 p1做根,找出所有最长的点qi,
2.2 p1 -> qi都是直径,找出p1->qi的公共LCA,  lcaq
2.3 任意选一个q1,找出所有最长的点pi
            lcap    lcaq
    p1 ---- Y-----X-----> q1
    p2  ----|     |____> q2
                 |-- q3

3. dep[lcaq] - dep[lcap] -> 边的数目
*/    

朴素算法

#include <iostream>
#include <vector>

#define N 200005

using namespace std;

typedef long long ll;

struct Edge {
    int y, w;
};

vector<Edge> g[N];
int n, fa[N], dep[N];
ll len[N], mx = 0;
int p[N], last;

void getMaxs() {
    last = 0;
    mx = 0;
    for (int i = 1; i <= n; i++)
        mx = max(mx, len[i]);

    for (int i = 1; i <= n; i++)
        if (len[i] == mx)
            p[++last] = i;
}

void dfs(int x, int _fa, int _dep, ll _len) {
    fa[x] = _fa;
    dep[x] = _dep;
    len[x] = _len;
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i].y, w = g[x][i].w;
        if (y == _fa) continue;
        dfs(y, x, _dep + 1, _len + w);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y])
        x = fa[x];
    while (x != y) {
        x = fa[x];
        y = fa[y];
    }
    return x;
}

int getCommonLca() {
    int x = p[1];
    for (int i = 2; i <= last; i++)
        x = lca(x, p[i]);
    return x;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        Edge e1 = {y, w};
        g[x].push_back(e1);
        Edge e2 = {x, w};
        g[y].push_back(e2);
    }
    dfs(1, 0, 1, 0);
    getMaxs();
    dfs(p[1], 0, 1, 0);
    getMaxs();
    int lca_u = getCommonLca();
    dfs(p[1], 0, 1, 0);
    getMaxs();
    int lca_v = getCommonLca();
    cout << mx << endl;
    cout << (dep[lca_v] - dep[lca_u]) << endl;
    return 0;
}

正解

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
struct Edge {
  int y, w;
};
const int N=200005;
int n,dep[N],fa[N], lgn, st[N][18];
ll dis[N], mx;
int p[N], last;
vector<Edge> g[N];

void calcMaxs() {
  last = 0, mx=0;
  for(int i=1; i<=n; i++)
    mx = max(mx, dis[i]);
  for(int i=1; i<=n; i++)
    if(dis[i]==mx)
      p[++last] = i;
}

void dfs(int x, int _fa, int _dep, ll _dis) {
  fa[x] = _fa;
  dep[x] = _dep;
  dis[x] = _dis;
  st[x][0] = _fa;
  for(int i=0; i<g[x].size(); i++) {
    int y = g[x][i].y, w=g[x][i].w;
    if(y == _fa) continue;
    dfs(y, x, _dep+1, _dis+w);
  }
}

void initSt() {
  for(int j=1; j<=lgn; j++)
    for(int i=1; i<=n; i++)
      st[i][j] = st[st[i][j-1]][j-1];
}

int lca(int x, int y) {
  if(dep[x]<dep[y]) swap(x, y);
  /*while(dep[x]>dep[y])
    x = fa[x];
  while(x!=y) {
    x = fa[x];
    y = fa[y];
  }*/
  int d = dep[x] - dep[y];
    for(int i=0; i<=lgn; i++)
      if((d>>i)&1)
          x = st[x][i];

  if(x==y) return x;

  for(int i=lgn; i>=0; i--) {
    if(st[x][i]==st[y][i]) continue;
    x = st[x][i];
    y = st[y][i];
  }
  return st[x][0];
}

int commonLca() {
  int cl = p[1];
  for(int i=2; i<=last; i++)
    cl = lca(cl, p[i]);
  return cl;
}

int main() {
  cin>>n;
  lgn = log2(n);
  for(int i=1; i<=n-1; i++) {
    int x, y, w;
    cin>>x>>y>>w;
    g[x].push_back((Edge){y, w});
    g[y].push_back((Edge){x, w});
  }
  //第一个端点u
  dfs(1, 0, 1, 0);
  calcMaxs();
  int u = p[1];

  //第二个端点v
  dfs(u, 0, 1, 0);
  calcMaxs();
  int v = p[1];
  //u为根的时候,p[i]的公共lca
  initSt();
  int lca_u = commonLca();

  //v为根的时候,p[i]的公共lca
  dfs(v, 0, 1, 0);
  calcMaxs();
  initSt();
  int lca_v = commonLca();

  //求公共边的数目, dep[lca_v]-dep[lca_u]
  cout<<mx<<endl;
  cout<<dep[lca_v]-dep[lca_u]<<endl;

  return 0;
}

评论

  • 还没有评论
作者: Zekrom 更新时间: 2019-05-11 15:37  在Ta的博客查看 举报    0  

直径必经边

说说主要思路:
首先必经边一定在一条直径上,枚举每一条点(记录前驱),dfs求出该点到非直径上的最长路(树的最长路一遍dfs即可,不用多此一举dijk),如果最长路到直径两端点的距离相同,我们意识到,这条最长路也是直径的一个选择,对于直径的起点和终点,如果都有这样一个断点,两个断点在直径上的距离就为必经边长度

注意:
枚举每一个点dfs求最长路时,在dfs过程中求出最长路的值,避免d数组的重新赋值和循环求出最长路,否则时间复杂度将上升到O(n^2),第一次没注意就这样T了
上代码 :

#include<iostream>
#include<cstdio>
#define N 200010
#include<queue>
#include<cmath>
#include<cstring> 
using namespace std;
int n,pos[N][2],head[N],route[N],num,tot,ans,s,e;
long long ls[N],re[N],d[N],dis[N] ,len,sum;
bool vis[N],v[N];
struct Edge{
    int v,next,val;
}edge[N*2]; 
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();};while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
inline void add(int x,int y,int z){edge[++tot].v=y;edge[tot].next=head[x];edge[tot].val=z;head[x]=tot;}
int bfs(int s){
    queue<int>q;q.push(s);memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)d[i]=0;memset(pos,0,sizeof(pos));long long maxn=0;
    int maxi;
    while(q.size()){
        int u=q.front();q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v,z=edge[i].val;
            if(vis[v])continue;
            d[v]=d[u]+z;
            q.push(v);
            pos[v][0]=u,pos[v][1]=z;
            if(d[v]>maxn)maxn=d[v],maxi=v; 
        }
    }
    len=maxn;
    return maxi;   //被机房称为毒瘤bfs写法求直径(他们都dfs6行orz)
}
void dfs(int s,int fa,int x){
    if(!head[s])return ;
    for(int i=head[s];i;i=edge[i].next){
        int to=edge[i].v,z=edge[i].val;
        if(to==fa||v[to])continue;
        d[to]=d[s]+z;
        dis[x]=max(dis[x],d[to]);  //dfs过程中求出dis
        dfs(to,s,x);
    }
}
int main(){
    n=read();
    for(int i=1;i<=n-1;i++){int x=read(),y=read(),z=read();add(x,y,z);add(y,x,z);}
    s=bfs(1);
    e=bfs(s);
    int t=e;
    route[++num]=e;
    v[e]=1;
    while(t!=s){//标记路径
        re[pos[t][0]]=re[t]+pos[t][1];    //在标记路径时求出直径上点到终点e距离,到起点s距离为直径长len-re[x]
        t=pos[t][0];
        route[++num]=t;
        v[t]=1;
    }
    for(int i=1;i<=num;i++){
        int x=route[i];
        d[x]=0;
        dfs(x,0,x);    //求出dis最长路
    }
    int tr=1;
    for(tr=1;tr<=num;tr++){
        int x=route[tr];
        if(dis[x]==len-re[x])break;  //如果到s距离为最长路,断点1set
    }
    int tl=num;
    for(tl=num;tl>=1;tl--){
        int x=route[tl];
        if(dis[x]==re[x])break;//同理断点2
    } 
    ans=abs(tr-tl);//这就是必经边数
    printf("%lld\n",len);
    printf("%d",ans);
    return 0;
}

评论

  • 1517460958dyc
    请合理使用MarkDown
作者: dfkdsmbd 更新时间: 2018-07-19 21:21  在Ta的博客查看 举报    0  

这是由一次题解都没有过审核的菜鸡为您带来的题解qwq 这个题我做的时候没有看题解,也没有想到所有直径交于一些连续的边这种事情,其实也很好想,但我的思路并不在这上面。 首先第一问可以dfs/bfs/dp,这个无所谓,但是要注意记得求出一种直径方案,便于我们处理第二问 我们首先分析,如果一个边一定在直径上的话,那么很显然,我去掉这个边之后,所分成的两棵子树,它们的直径一定小于原树的直径,不然这个边就不一定在直径上了,有可能会存在别的直径方案不覆盖这条边。 那么问题可以转化成求去掉某种直径的某一条边后,新形成的两棵子树的直径,这个东西如果暴力枚举去掉哪条边的话,很显然坠坏的时间复杂度是n^2的。然后我们想这个地方有没有重复的,可以优化的部分。回想一下树形dp求树的直径的过程,我们求一棵树的直径的时候,它的所有子树一定都是处理好的。那么很显然我们如果断开一条边的时候,有直径起点的那一部分子树,很显然可以通过以直径终点为根跑树形dp来处理看,反之亦然。 这样我们就轻松去掉了一个n,总的时间复杂度变为了O(n)。当然两边bfs+两边dfs会使得常数比较大,但是总的来说还是很轻松的就能过的。 如果有写的不好的地方请多指教qwq。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int n, s, t, he, ta, tot = -1, pos, q[200020], head[200020], pre[200020], lx, ly, lz; 

struct in
{
    int to, ne; lo co;
}ter[400040];

inline void build(int f, int l, lo c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], c}, head[l] = tot;
}

lo ans, sx[200020], tx[200020], sy[200020], ty[200020], de[200020];//x 联通块直径 y最深深度 

inline void bfs(int x)
{
    memset(de, 0, sizeof(de)), memset(pre, 0, sizeof(pre));
    de[q[he = ta = 0] = x] = 1, pos = 0;
    while(he <= ta)
    {
        int qaq = q[he ++]; pos = (de[pos] < de[qaq]) ? qaq : pos;//更新最深的点 
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0)
                pre[to] = qaq, de[q[++ ta] = to] = de[qaq] + ter[i].co;
        }
    }
}

void dfs(lo *a, lo *b, int no, int fa)
{
    lo lx = 0, ly = 0;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa)
            continue;
        dfs(a, b, to, no);
        b[no] = (b[no] < b[to] + ter[i].co) ? b[to] + ter[i].co : b[no];
        if(lx < b[to] + ter[i].co)
            ly = lx, lx = b[to] + ter[i].co;
        else if(ly < b[to] + ter[i].co)
            ly = b[to] + ter[i].co; 
        a[no] = (a[no] < a[to]) ? a[to] : a[no];//维护子树内部的直径 
    } 
    a[no] = (lx + ly < a[no]) ? a[no] : lx + ly;
}

int main()
{
    re(n); memset(head, -1, sizeof(head)); s = t = 0;
    memset(sx, 0, sizeof(sx)), memset(sy, 0, sizeof(sy));
    memset(tx, 0, sizeof(tx)), memset(ty, 0, sizeof(ty));
    for(ri i = 1; i < n; i ++)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    bfs(1), s = pos, bfs(s), t = pos;//两边bfs确定任意一条直径 
    dfs(sx, sy, s, 0), dfs(tx, ty, t, 0);//分别以起点和终点为根再去处理子树的信息 
    for(ri i = t; i != s; i = pre[i])
        if(tx[pre[i]] < sx[s] && sx[i] < sx[s])//如果删除这条边之后,两个子树内的直径都小于原树直径 
           ans ++;//说明这个边一定被所有直径经过 
    printf("%lld\n%lld", sx[s], ans);
}

评论

  • 还没有评论
作者: 叫我总攻さま 更新时间: 2017-11-30 13:07  在Ta的博客查看 举报    0  
#include<stdio.h>
#define maxn 233333
int father[maxn],head[maxn],n,tot,l,r,p;
long long maxd,dep[maxn];//最长与深度
bool isofd[maxn],flag;//对第一条直径(标准直径)的点标记 
struct hhh{int to,w,next;}edge[2*maxn];//邻接表
void add(int x,int y,int z)//加边
{
    edge[++tot].to=y;      edge[tot].w=z;
    edge[tot].next=head[x];    head[x]=tot;
}
void dfs1(int u,int fa)//算直径的深搜 
{
    father[u]=fa;//记爸爸 
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;if(v==fa)    continue;//只能遍历儿子 
        dep[v]=dep[u]+edge[i].w;
        if(dep[v]>maxd)    p=v,maxd=dep[v];//最远(深)的点和距离 
        dfs1(v,u);
    }
}
void dfs2(int u,int fa)//搜索标准直径上每一个点的子树深度 
{
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;if(v==fa||isofd[v])    continue;
        dep[v]=dep[u]+edge[i].w;//dep没用了,随便改 
        if(dep[v]>maxd)    maxd=dep[v];//最深 
        dfs2(v,u);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);        add(b,a,c);
    }
    dfs1(1,0);    l=p;//以任意一个点为根搜最深作为标准直径左端点 
    dep[p]=maxd=0;    dfs1(l,0);    r=p;//以左端点为根搜最深即为又端点 
    printf("%lld\n",maxd);
    //喜:直径结束!!QAQ
    for(int i=r;i;i=father[i])    isofd[i]=true;//标记标准诗经上的点
    int ll=l,rr=r;                    //避免搜索的深度与标准直径重复 
    for(int i=father[rr];i!=ll;i=father[i])
    {
        int ld=dep[i],rd=dep[rr]-dep[i];//该点到左右端点的距离 
        dep[i]=maxd=0;//dep过去就没用了,清空状态,搜索子树深度 
        dfs2(i,0);
        if(maxd==rd)    r=i;
        //如果子树深度与到右端点的距离相同,那么意味着从这点还有其他直径分出,缩短树干右端点 
        if(maxd==ld&&!flag)    flag=true,l=i;//因为从右遍历,左端点剪一次为最佳 
    }
    maxd=1;//改记缩短后的r~l经过边数
    for(int i=father[r];i!=l;i=father[i])    maxd++;
    printf("%d\n",maxd);
    return 0; 
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。