19_08_10[校内训练]割图

题意

给一个图,对每个点求(删去一条出边)的(到一号节点的(最大的(最短路的长度))),有边权。n,m≤1E5。

方便起见,没有重边和自环。


 

思考

先建出最小生成树,可以发现每次一定要删去连向父亲的边。此后,会沿着它的出边走向其他或自己的祖先,再算上原先图的最短路长度。

那么对于每个节点维护一个堆,含义为从该点出发,沿着出边(不包括连向父亲的)走一步,再沿原图的最短路走向1号节点的所有路径的长度,按秩合并。合并时要给自己的堆整体加上连向它的边权,其他子树的堆清空标记。

注意一条出边可能连向祖先,因此在查询答案时要去掉原本出边的点在子树中的答案。

此题解没有写   有重边的情况,但代码中考虑到了。

复杂度O(nlog^2)


 

代码

19_08_10[校内训练]割图
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long int ll;
  4 typedef pair<ll,int> pr;
  5 const ll inf=1E15;
  6 const int maxn=1E6+5;
  7 int n,m;
  8 int pre[maxn],w[maxn],bel[maxn],sum[maxn],son[maxn],dfn[maxn],low[maxn];
  9 int TI;
 10 ll dis[maxn],ans[maxn],tag[maxn],down[maxn];
 11 bool vis[maxn];
 12 priority_queue<pr,vector<pr>,greater<pr> >wait[maxn];
 13 map<pair<int,int>,int>appear;
 14 map<pair<int,int>,int>min1,min2;
 15 pair<int,int> M(int x,int y)
 16 {
 17     if(x>y)
 18         swap(x,y);
 19     return make_pair(x,y);
 20 }
 21 struct edge
 22 {
 23     int to,next;
 24     ll w;
 25 };
 26 struct graph
 27 {
 28     int size,head[maxn*2];
 29     edge E[maxn*2];
 30     inline void add(int u,int v,int w)
 31     {
 32         E[++size].to=v;
 33         E[size].next=head[u];
 34         E[size].w=w;
 35         head[u]=size;
 36     }
 37     void spfa()
 38     {
 39         for(int i=1;i<=n;++i)
 40             dis[i]=inf;
 41         queue<int>Q;
 42         Q.push(1);
 43         dis[1]=0;
 44         vis[1]=1;
 45         while(!Q.empty())
 46         {
 47             int u=Q.front();
 48             Q.pop();
 49             vis[u]=0;
 50             for(int i=head[u];i;i=E[i].next)
 51             {
 52                 int v=E[i].to;
 53                 ll nw=dis[u]+E[i].w;
 54                 if(nw>=dis[v])
 55                     continue;
 56                 dis[v]=nw;
 57                 pre[v]=u;
 58                 w[v]=E[i].w;
 59                 if(!vis[v])
 60                     vis[v]=1,Q.push(v);
 61             }
 62         }
 63     }
 64     void init(int u)
 65     {
 66         low[u]=dfn[u]=++TI;
 67         sum[u]=1;
 68         for(int i=head[u];i;i=E[i].next)
 69         {
 70             int v=E[i].to;
 71             init(v);
 72             low[u]=low[v];
 73             sum[u]+=sum[v];
 74             if(sum[v]>sum[son[u]])
 75                 son[u]=v,down[u]=E[i].w;
 76         }
 77     }
 78 }G,T;
 79 inline bool in(int v,int u)
 80 {
 81     return dfn[u]<=dfn[v]&&dfn[v]<=low[u];
 82 }
 83 void dfs(int u,int F)
 84 {
 85     if(son[u]==0)
 86     {
 87         bel[u]=u;
 88         for(int i=G.head[u];i;i=G.E[i].next)
 89         {
 90             int v=G.E[i].to;
 91             if(v==F)
 92                 continue;
 93             wait[bel[u]].push((pr){G.E[i].w+dis[v],v});
 94         }
 95         if(wait[bel[u]].empty())
 96         {
 97             ans[u]=-1;
 98             if(appear[M(u,F)]>=2)
 99                 ans[u]=dis[u]-min1[M(u,F)]+min2[M(u,F)];
100         }
101         else
102             ans[u]=wait[bel[u]].top().first;
103         return;
104     }
105     else
106     {
107         dfs(son[u],u);
108         bel[u]=bel[son[u]];
109         tag[bel[u]]+=down[u];
110     }
111     for(int i=G.head[u];i;i=G.E[i].next)
112     {
113         int v=G.E[i].to;
114         if(v==F||in(v,u))
115             continue;
116         wait[bel[u]].push((pr){G.E[i].w+dis[v]-tag[bel[u]],v});
117     }
118     for(int i=T.head[u];i;i=T.E[i].next)
119     {
120         int v=T.E[i].to;
121         if(v==F||v==son[u])
122             continue;
123         dfs(v,u);
124         while(!wait[bel[v]].empty())
125         {
126             pr A=wait[bel[v]].top();
127             wait[bel[v]].pop();
128             ll x=A.first;
129             wait[bel[u]].push((pr){x+tag[bel[v]]+T.E[i].w-tag[bel[u]],A.second});
130         }
131     }
132     while(!wait[bel[u]].empty()&&in(wait[bel[u]].top().second,u))
133         wait[bel[u]].pop();
134     if(wait[bel[u]].empty())
135         ans[u]=-1;
136     else
137         ans[u]=wait[bel[u]].top().first+tag[bel[u]];
138     if(appear[M(u,F)]>=2)
139         ans[u]=min(ans[u],dis[u]-min1[M(u,F)]+min2[M(u,F)]);
140 }
141 int main()
142 {
143 //    freopen("rebirth25.in","r",stdin);
144 //    freopen("rebirth.out","w",stdout);
145     ios::sync_with_stdio(false);
146     int num;
147     cin>>num;
148     cin>>n>>m;
149     for(int i=1;i<=m;++i)
150     {
151         int x,y,z;
152         cin>>x>>y>>z;
153         if(x==y)
154             continue;
155         if(min1[M(x,y)]==0)
156             min1[M(x,y)]=z;
157         else if(z<min1[M(x,y)])
158             min2[M(x,y)]=min1[M(x,y)],min1[M(x,y)]=z;
159         else if(min2[M(x,y)]==0)
160             min2[M(x,y)]=z;
161         else if(z<min2[M(x,y)])
162             min2[M(x,y)]=z;
163         ++appear[M(x,y)];
164         G.add(x,y,z);
165         G.add(y,x,z);
166     }
167     G.spfa();
168     for(int i=2;i<=n;++i)
169         T.add(pre[i],i,w[i]);
170     T.init(1);
171     dfs(1,1);
172     ans[1]=0;
173     for(int i=1;i<=n;++i)
174         cout<<ans[i]<<" ";
175     cout<<endl;
176     return 0;
177 }
View Code

 

上一篇:LG2463/BZOJ4698 「SDOI2008」Sandy的卡片 后缀数组


下一篇:BZOJ.4144.[AMPPZ2014]Petrol(Kruskal重构树)