Luogu

BZOJ

分析

此代码建图部分有问题,在某种特殊的情况下会建出错误的最短路树!

然而并没有这种数据,懒得改了


这题应该比较好想。

首先跑$\mathrm{Dijkstra}$求出最短路,然后构建最短路树。这一部分比较简单。

然后,点分治求答案。这一部分比较套路。

具体怎么点分治:

考虑经过$u$这个点的路径对答案的贡献。用$cross[x]$表示经过点$u$,包含$x$条边的路径的信息(信息包括:最长长度、路径数量)。然后处理$u$的每个子节点$v$时,处理出以$v$为根的子树的路径信息。

对于一条包含$k-1$条边的路径,直接更新答案;对于一条包含边数小于$k-1$的路径,设它包含$x$条边,那将它的信息与$cross[k-1-x]$合并到一起更新答案。

这两段话摘自Ebola的题解,因为我感觉自己写不清楚

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30000+10;
const int M=60000+10;

int n,m,k;
int dis[N];

struct Edge { int v,w,nxt; };
Edge e[M<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

namespace Build_Tree {
    struct HeapNode {
        int u,d;
        bool operator <(const HeapNode& rhs) const {
            return d>rhs.d;
        }
    };

    priority_queue<HeapNode> Q;
    
    inline void dijkstra() {
        memset(dis,0x3f,sizeof(dis));
        Q.push((HeapNode){1,0}); dis[1]=0;
        while (!Q.empty()) {
            HeapNode fr=Q.top(); Q.pop();
            int u=fr.u,d=fr.d;
            if (dis[u]!=d) continue;
            for (re int i=head[u];i;i=e[i].nxt) {
                int v=e[i].v,w=e[i].w;
                if (dis[u]+w<dis[v]) {
                    dis[v]=dis[u]+w;
                    Q.push((HeapNode){v,dis[v]});
                }
            }
        }
    }

    int vis[N],x[N],y[N],z[N],tot=0;
    inline void build() {
        vis[1]=1;
        for (re int u=1;u<=n;++u)
            for (re int i=head[u];i;i=e[i].nxt) {
                int v=e[i].v,w=e[i].w;
                if (!vis[v]&&dis[u]+w==dis[v]) {
                    x[++tot]=u,y[tot]=v,z[tot]=w;
                    vis[v]=1;
                    if (tot==n-1) break;
                }
            }
        memset(head,0,sizeof(head)); cnt=0;
        for (re int i=1;i<=tot;++i) {
            addEdge(x[i],y[i],z[i]);
            addEdge(y[i],x[i],z[i]);
        }
    }

    inline void work() {
        dijkstra(); build();
    }
}

namespace Main {
    int vis[N];
    int sum,maxd;
    int sz[N],f[N],root;
    inline void getroot(int u,int fa) {
        sz[u]=1,f[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (vis[v]||v==fa) continue;
            getroot(v,u); sz[u]+=sz[v],f[u]=max(f[u],sz[v]);
        }
        f[u]=max(f[u],sum-f[u]);
        if (!root||f[u]<f[root]) root=u;
    }

    int tot=0;
    pair<int,int> d[N],now[N],cross[N];
    pair<int,int> ans;
    inline void dfs(int u,int fa) {
        now[++tot]=d[u];
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (v==fa||vis[v]) continue;
            d[v].first=d[u].first+1;
            d[v].second=d[u].second+w;
            dfs(v,u);
        }
    }
    
    inline void calc(int u,int d0) {
        d[u].first=1,d[u].second=d0;
        tot=0; dfs(u,0);
        for (re int i=1;i<=tot;++i) {
            int rest=k-now[i].first-1,w=now[i].second;
            if (now[i].first<k-1) {
                int t1=cross[rest].first,t2=cross[rest].second;
                if (w+t2>ans.first) ans=make_pair(w+t2,t1);
                else if (w+t2==ans.first) ans.second+=t1;
            }
            if (now[i].first==k-1) {
                if (w>ans.first) ans=make_pair(w,1);
                else if (w==ans.first) ++ans.second;
            }
        }
        for (re int i=1;i<=tot;++i) {
            if (now[i].first<k) {
                int num=now[i].first;
                if (now[i].second>cross[num].second) cross[num]=make_pair(1,now[i].second);
                else if (now[i].second==cross[num].second) ++cross[num].first;
                maxd=max(maxd,num);
            }
        }
    }

    inline void solve(int u) {
        vis[u]=1; maxd=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (!vis[v]) calc(v,w);
        }
        /*这个地方要是全部清空在BZOJ上会TLE*/
        memset(cross,0,sizeof(pair<int,int>)*(maxd+1));
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (vis[v]) continue;
            sum=sz[v]; root=0;
            getroot(v,u); solve(root);
        }
    }
    
    inline void work() {
        sum=n; getroot(1,0); solve(root);
        printf("%d %d\n",ans.first,ans.second);
    }
}

int main() {
    n=read(),m=read(),k=read();
    for (re int i=1,u,v,w;i<=m;++i) {
        u=read(),v=read(),w=read();
        addEdge(u,v,w); addEdge(v,u,w);
    }
    Build_Tree::work();
    Main::work();
    return 0;
}
最后修改:2019 年 09 月 24 日 10 : 03 PM