题解 P2993 【[FJOI2014]最短路径树问题】

· · 题解

这是强行拼题啊。不太擅长点分的我都做出来这题，不过码起来是真的难受，说实话我感觉6K+的那种数据结构题码起来都非常舒服，但这种题就莫名很难受

首先是要求出最短路图。具体地，先以1为源点做一遍单源最短路，若一条边e满足d[u]+e.capa=d[v]，则这条边在最短路图中。然后这题要求建字典序最小的树吧，那就用邻接表存图，把每个点的出边按指向的点从小到大排序，然后dfs建树就是了。这个数据规模要卡起spfa来是会炸的，不知道出题人卡不卡，反正保险起见我写了dij

那至于题目要求的答案吧，就是点分的经典套路。对于每个点u，考虑经过u这个点的路径对答案的贡献。可以用tmp[x]表示经过点u，包含x条边的路径的信息（信息包括：最长长度、路径数量）。然后处理u的每个子节点v时，处理出以v为根的子树的路径信息。对于一个包含k-1条边的路径，直接更新答案。对于一个包含边数少于k-1的路径，设它包含x条边，那将它的信息与tmp[k-1-x]合并到一起来更新答案。tmp数组在每个分治环节都要清空，千万不要整个memset！

具体还是看代码吧，一看就懂。反正我码着非常难受就是了

#include<bits/stdc++.h>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
using namespace std;

const int S=(1<<20)+5;
char buf[S],*H,*T;
inline char Get()
{
    if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
    if(H==T) return -1;return *H++;
}
inline int read()
{
    int x=0;char c=Get();
    while(!isdigit(c)) c=Get();
    while(isdigit(c)) x=x*10+c-'0',c=Get();
    return x;
}

typedef pair<int,int> pii;
const int N=30010;
struct Edge{int to,capa,next;} e[N<<1];
int h[N],n,m,K,esum=0;
vector<pii> G[N];
priority_queue<pii> q;
bool vis[N];int dis[N];
int sum=0,root,mxsz[N];
pii ans,d[N],now[N],cross[N];
int sz[N],mxd,tot;

void add_edge(int u,int v,int w)
{
    e[++esum].to=v;
    e[esum].capa=w;
    e[esum].next=h[u];
    h[u]=esum;
}

void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    q.push(MP(0,1));dis[1]=0;
    while(!q.empty())
    {
        pii tmp=q.top();q.pop();
        int u=tmp.SE,w=-tmp.FR;
        if(vis[u]) continue;
        vis[u]=1;
        for(pii pr : G[u])
            if(w+pr.SE<dis[pr.FR])
            {
                dis[pr.FR]=w+pr.SE;
                q.push(MP(-dis[pr.FR],pr.FR));
            }
    }
}

void find(int u,int fa)
{
    sz[u]=1;mxsz[u]=0;
    for(int t=h[u];t;t=e[t].next)
    {
        int v=e[t].to;
        if(v==fa||vis[v]) continue;
        find(v,u);sz[u]+=sz[v];
        mxsz[u]=max(mxsz[u],sz[v]);
    }
    mxsz[u]=max(mxsz[u],sum-sz[u]);
    if(mxsz[u]<mxsz[root]) root=u;
}

void dfs(int u,int fa)
{
    now[++tot]=d[u];
    for(int t=h[u];t;t=e[t].next)
    {
        int v=e[t].to;
        if(v==fa||vis[v]) continue;
        d[v].SE=d[u].SE+e[t].capa;
        d[v].FR=d[u].FR+1;dfs(v,u);
    }
}

void gao(int u,int w)
{
    d[u].FR=1;d[u].SE=w;
    tot=0;dfs(u,0);
    for(int i=1;i<=tot;i++)
    {
        int rest=K-now[i].FR-1,w=now[i].SE;
        if(now[i].FR<K-1)
        {
            int t1=cross[rest].FR,t2=cross[rest].SE;
            if(w+t2>ans.FR) ans=MP(w+t2,t1);
            else if(w+t2==ans.FR) ans.SE+=t1;
        }
        if(now[i].FR==K-1)
        {
            if(w>ans.FR) ans=MP(w,1);
            else if(w==ans.FR) ans.SE++;
        }
    }
    for(int i=1;i<=tot;i++)
        if(now[i].FR<=K-1)
        {
            int num=now[i].FR;
            if(now[i].SE>cross[num].SE) cross[num]=MP(1,now[i].SE);
            else if(now[i].SE==cross[num].SE) cross[num].FR++;
            mxd=max(mxd,num);
        }
}

void solve(int u)
{
    vis[u]=1;mxd=0;
    for(int t=h[u];t;t=e[t].next)
        if(!vis[e[t].to]) gao(e[t].to,e[t].capa);
    memset(cross,0,sizeof(pii)*(mxd+2));
    for(int t=h[u];t;t=e[t].next)
    {
        int v=e[t].to;
        if(vis[v]) continue;
        sum=sz[v];root=0;
        find(v,u);solve(root);
    }
}

void build(int u)
{
    vis[u]=1;
    for(pii pr : G[u])
    {
        int v=pr.FR,w=pr.SE;
        if(vis[v]||dis[u]+w!=dis[v]) continue;
        add_edge(u,v,w);add_edge(v,u,w);build(v);
    }
}

int main()
{
    int u,v,w;
    n=read();m=read();K=read();
    for(int i=1;i<=m;i++)
    {
        u=read();v=read();w=read();
        G[u].PB(MP(v,w));
        G[v].PB(MP(u,w));
    }
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
    dijkstra();memset(vis,0,sizeof(vis));build(1);
    memset(vis,0,sizeof(vis));
    sum=mxsz[0]=n;root=0;
    find(1,0);solve(root);
    printf("%d %d\n",ans.FR,ans.SE);
    return 0;
}