做企业网站的意义,河北建设集团园林网站,宣城市建设银行网站,wordpress图片0x0容易想到把边当成点重建图跑最短路。将每条边拆成入边和出边#xff0c;作为新图中的两个点#xff0c;由出边向入边连边权为原费用的边。对于原图中的每个点#xff0c;考虑由其入边向出边连边。直接暴力两两连边当然会被卡掉#xff0c;注意到其边权是trie上lca的深度作为新图中的两个点由出边向入边连边权为原费用的边。对于原图中的每个点考虑由其入边向出边连边。直接暴力两两连边当然会被卡掉注意到其边权是trie上lca的深度由lca转rmq的做法可知两点lca即为欧拉序区间中它们之间深度最小的点于是跑出欧拉序后对入边出边的前后缀建虚点连边即可。当然每次连边时都需要将trie上有用的点提取出来建虚树即可。 #includeiostream
#includecstdio
#includecmath
#includecstdlib
#includecstring
#includealgorithm
#includevector
#includequeue
using namespace std;
#define ll long long
#define N 50010
#define inf 2000000000
#define in(i) (i*2n)
#define out(i) (i*2n-1)
char getc(){char cgetchar();while ((cA||cZ)(ca||cz)(c0||c9)) cgetchar();return c;}
int gcd(int n,int m){return m0?n:gcd(m,n%m);}
int read()
{int x0,f1;char cgetchar();while (c0||c9) {if (c-) f-1;cgetchar();}while (c0c9) x(x1)(x3)(c^48),cgetchar();return x*f;
}
int T,n,m,k,p[N],t;
struct data{int to,nxt,len,s;
}edge[N];
vectorint in_edge[N];
namespace trie
{int p[N],t,fa[N][18],deep[N],dfn[N],cnt;struct data{int to,nxt;}edge[N];void clear(){memset(p,0,sizeof(p));cntt0;}void addedge(int x,int y){t;edge[t].toy,edge[t].nxtp[x],p[x]t;}void dfs(int k){dfn[k]cnt;for (int ip[k];i;iedge[i].nxt){deep[edge[i].to]deep[k]1;fa[edge[i].to][0]k;dfs(edge[i].to);}}void build(){fa[1][0]1;dfs(1);for (int j1;j18;j)for (int i1;ik;i)fa[i][j]fa[fa[i][j-1]][j-1];}int lca(int x,int y){if (deep[x]deep[y]) swap(x,y);for (int j17;~j;j--) if (deep[fa[x][j]]deep[y]) xfa[x][j];if (xy) return x;for (int j17;~j;j--) if (fa[x][j]!fa[y][j]) xfa[x][j],yfa[y][j];return fa[x][0];}
}
namespace graph
{int p[N6],t,cnt,dis[N6];bool flag[N6];struct data{int to,nxt,len;}edge[N7];struct data2{int x,d;bool operator (const data2a) const{return da.d;}};priority_queuedata2 q;void addedge(int x,int y,int z){t;edge[t].toy,edge[t].nxtp[x],edge[t].lenz,p[x]t;}void clear(){cntnm*2;t0;memset(p,0,sizeof(p));}void dijkstra(){for (int i1;icnt;i) dis[i]inf;dis[1]0;memset(flag,0,sizeof(flag));q.push((data2){1,0});for (;;){while (!q.empty()flag[q.top().x]) q.pop();if (q.empty()) break;data2 xq.top();q.pop();flag[x.x]1;for (int ip[x.x];i;iedge[i].nxt)if (dis[x.x]edge[i].lendis[edge[i].to]){dis[edge[i].to]dis[x.x]edge[i].len;q.push((data2){edge[i].to,dis[edge[i].to]});}}}
}
namespace virtual_tree
{int a[N],tot,stk[N],id[N1],top,p[N],x[N],y[N],idin[N1],idout[N1],pre[N1],suf[N1],t,cnt;struct data{int to,nxt;}edge[N1];void addedge(int u,int v){t;x[t]u,y[t]v;}void clear(){tottoptcnt0;}void push(int x){a[tot]x;}bool cmp(const inta,const intb){return trie::dfn[a]trie::dfn[b];}void dfs(int k){id[cnt]k;idin[k]graph::cntcnt;for (int ip[k];i;iedge[i].nxt){dfs(edge[i].to);id[cnt]k;}}void build(){if (tot0) return;sort(a1,atot1,cmp);totunique(a1,atot1)-a-1;stk[top]1;for (int i1(a[1]1);itot;i){int ltrie::lca(a[i],stk[top]);if (stk[top]!l){while (top1trie::deep[stk[top-1]]trie::deep[l]) addedge(stk[top-1],stk[top]),top--;if (stk[top]!l) addedge(l,stk[top]);stk[top]l;}stk[top]a[i];}while (top1) addedge(stk[top-1],stk[top]),top--;for (int i1;it;i) p[x[i]]p[y[i]]0;for (int i1;it;i) edge[i].toy[i],edge[i].nxtp[x[i]],p[x[i]]i;dfs(1);for (int i1;icnt;i) idout[id[i]]idin[id[i]]cnt;graph::cntcnt1;for (int i1;icnt;i){pre[i]graph::cnt;graph::addedge(idin[id[i]],pre[i],0);if (i1) graph::addedge(pre[i-1],pre[i],0);}for (int icnt;i1;i--){suf[i]graph::cnt;graph::addedge(suf[i],idout[id[i]],0);if (icnt) graph::addedge(suf[i],suf[i1],0);}for (int i1;icnt;i) graph::addedge(pre[i],suf[i],trie::deep[id[i]]);for (int i1;icnt;i){pre[i]graph::cnt;graph::addedge(pre[i],idout[id[i]],0);if (i1) graph::addedge(pre[i],pre[i-1],0);}for (int icnt;i1;i--){suf[i]graph::cnt;graph::addedge(idin[id[i]],suf[i],0);if (icnt) graph::addedge(suf[i1],suf[i],0);}for (int i1;icnt;i) graph::addedge(suf[i],pre[i],trie::deep[id[i]]);}
}
int main()
{
#ifndef ONLINE_JUDGEfreopen(bzoj4912.in,r,stdin);freopen(bzoj4912.out,w,stdout);const char LL[]%I64d\n;
#elseconst char LL[]%lld\n;
#endifTread();while (T--){nread(),mread(),kread();memset(p,0,sizeof(p));t0;for (int i1;in;i) in_edge[i].clear();for (int i1;im;i){int xread(),yread(),lenread(),sread();t;edge[t].toy,edge[t].nxtp[x],edge[t].lenlen,edge[t].ss,p[x]t;}trie::clear();for (int i1;ik;i){int xread(),yread(),zread();trie::addedge(x,y);}trie::build();graph::clear();for (int ip[1];i;iedge[i].nxt)graph::addedge(1,out(i),0);for (int i1;im;i) if (edge[i].to!1) graph::addedge(in(i),edge[i].to,0);for (int i1;im;i) graph::addedge(out(i),in(i),edge[i].len);for (int i1;im;i) in_edge[edge[i].to].push_back(i);for (int i1;in;i){virtual_tree::clear();for (int j0;jin_edge[i].size();j) virtual_tree::push(edge[in_edge[i][j]].s);for (int jp[i];j;jedge[j].nxt) virtual_tree::push(edge[j].s);virtual_tree::build();for (int j0;jin_edge[i].size();j) graph::addedge(in(in_edge[i][j]),virtual_tree::idin[edge[in_edge[i][j]].s],0);for (int jp[i];j;jedge[j].nxt) graph::addedge(virtual_tree::idout[edge[j].s],out(j),0);}graph::dijkstra();for (int i2;in;i) printf(%d\n,graph::dis[i]);}return 0;
}转载于:https://www.cnblogs.com/Gloid/p/10347036.html
