喜欢的话就坚持吧

10月 18

0.00 avg. rating (0% score) - 0 votes

题目大意

给你一张n个点m条边的图,让你求出从1号节点出发到所有点的最短路,问不能选每条最短路到终点的前一条边时,1号点到所有点的最短路分别是多少?无解输出-1,保证原来的最短路唯一。
n<=100,000 m<=200,000;


一看就是道不可做题,
首先想到模拟题意,大概O(nmlogn)的复杂度
然后手玩样例….
我们可以先跑出最短路树(假设你已经算出)
发现对于他询问的每个点i,都是切掉了i的父亲边。
这时显然最短路树变成了两个子树,
假如i所在的子树为T,另一半为S
那么1到i的最短路肯定是从1到S中某一点到T中某一点到i;
假设我们最开始求出的最短路数组为dis[];
假设S中某一点为x,T中某一点是y,且边(x,y)不是i的父亲边。
那么切掉i的父亲边时答案就是

dis[x]+dis[y]-dis[i]+val(x,y)

然后我们只需要维护这个最小值即可。
然后发现我们只需要找在两个不同子树中

min(dis[x]+dis[y]+val(x,y))

可以考虑树形dp什么的。
假如我在考虑某个叶子节点a,那么它所能贡献的答案就是(a,?)?表示与a相连的点。
那么我们只需要在这些点里找到合适?,使上面的式子最小即可,
然后我只会一种显然的做法,
每个点开一个可并堆,记录上面式子的值,
然后一直考虑根节点,不合法就pop掉。
然后把堆合并一下就好。
然后如何判不合法的?并查集可以快速判断两个点是否在同一子树。
最后说几句。
1. 因为不用可持久化,写配对堆更快
2. 网上大部分都是写了一个什么lca,sort什么的做法。我是没仔细看。

然后是代码。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cctype>
using namespace std;
const int N=100005;
const int INF=0x3f3f3f3f;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
struct data
{
    int u,v,nxt,val,path;
}edge[N<<2];
int cnt,alist[N];
inline void add(int u,int v,int val){edge[++cnt]=(data){u,v,alist[u],val,0},alist[u]=cnt;}

int n,m;
int vis[N],dis[N];
struct nod
{
    int num,val;
    friend bool operator <(nod a,nod b){return a.val>b.val;}
};
inline void dj(int x)
{
    priority_queue<nod> q;
    memset(dis,INF,sizeof dis);
    dis[x]=0;q.push((nod){x,0});
    while(!q.empty())
    {
        int now=q.top().num;q.pop();
        if(vis[now]) continue;
        vis[now]=true;
        for(register int i=alist[now];i;i=edge[i].nxt)
        {
            int v=edge[i].v;int val=edge[i].val;
        //  printf("v=%d now=%d\n",v,now);
            if(dis[v]>dis[now]+val)
            {
                dis[v]=dis[now]+val;
                q.push((nod){v,dis[v]});
            }
        }
    }
}

struct project
{
    int l,r,h;
    data eg;
}tr[N<<2];
int root[N],fa[N],ans[N];
int fafa[N];
inline int f(int x){return !fafa[x]?x:fafa[x]=f(fafa[x]);}
inline int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(tr[x].eg.path>tr[y].eg.path) swap(x,y);
    tr[x].r=merge(tr[x].r,y);
    if(tr[tr[x].l].h<tr[tr[x].r].h) swap(tr[x].l,tr[x].r);
    tr[x].h=tr[tr[x].r].h+1;
    return x;
}
inline void dp(int x)
{
    if(vis[x]) return; vis[x]=true;
    for(register int i=alist[x];i;i=edge[i].nxt)
    {
        int v=edge[i].v;int val=edge[i].val;
        if(dis[x]+val==dis[v])
        {
            if(vis[v]) continue;
            fa[v]=x;dp(v);
            root[x]=merge(root[x],root[v]);
            fafa[f(v)]=f(x);
        }
    }
    for(register int i=alist[x];i;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(f(v)!=x&&v!=fa[x])
        {
            root[x]=merge(root[x],i);
        }
    }
    while(root[x]&&f(tr[root[x]].eg.v)==x) root[x]=merge(tr[root[x]].l,tr[root[x]].r);
    if(root[x]) ans[x]=tr[root[x]].eg.path-dis[x];
    else ans[x]=-1;
}
int main()
{
    n=read();m=read();
    for(register int i=1,x,y,z;i<=m;++i)
    {
        x=read();y=read();z=read();
        add(x,y,z);add(y,x,z);
    }
    dj(1);
//  for(int i=1;i<=n;++i) printf("%d ",dis[i]);
    for(register int i=1;i<=cnt;++i)
    {
        tr[i].eg=edge[i];
        tr[i].eg.path=dis[tr[i].eg.u]+dis[tr[i].eg.v]+tr[i].eg.val;
    }memset(vis,false,sizeof vis);
    dp(1);
    for(register int i=2;i<=n;++i) print(ans[i]);
    return Ot(),0;
}
0.00 avg. rating (0% score) - 0 votes
  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注