【SDOI2017】天才黑客

這題太神了。

先模Claris 大神的題解。

首先我們要將邊轉(zhuǎn)換為點(diǎn)。如果暴力連邊就會(huì)有\(m^2\)的邊，于是我們考慮優(yōu)化建圖。

難點(diǎn)在于快速得到兩個(gè)邊的串的\(lcp\)，也就是\(trie\)樹(shù)上的\(lca\)。我們將一堆點(diǎn)按\(dfs\)序排序，然后\(a\)到\(b\)的\(lca\)就是排序后\(min\{lca(a,a+1),lca(a+1,a+2)...lca(b-1,b)\}\)，這里的\(min\)是深度最小。

對(duì)于原圖上的點(diǎn)\(i\)，我們就將所有的邊按\(dfs\)序拍好序，再?gòu)?fù)制一倍的虛點(diǎn)，相鄰的實(shí)點(diǎn)和虛點(diǎn)連權(quán)值為\(0\)的邊。每個(gè)實(shí)點(diǎn)向下一個(gè)點(diǎn)對(duì)應(yīng)的虛點(diǎn)連權(quán)值為\(dep_{lca}\)的邊。

然后還要反方向建相同的邊，不過(guò)不能建在一張圖上。

這道題中關(guān)于處理一堆點(diǎn)兩兩之間\(lca\)的方法值得掌握。

代碼：

#include<bits/stdc++.h> #define ll long long #define N 400005using namespace std; inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m,k; int tot,TOT; int w[N],t[N]; ll dis[N]; ll ans[N]; vector<int>st[N]; vector<int>e[N]; struct road {int to,next;ll c; }s[N*15]; int h[N],cnt; void add(int i,int j,int c) {s[++cnt]=(road) {j,h[i],c};h[i]=cnt;}int id,dfn[N]; void Init() {cnt=0;id=0;memset(h,0,sizeof(h));memset(t,0,sizeof(t));memset(w,0,sizeof(w));memset(dis,0x3f,sizeof(dis));for(int i=1;i<=k;i++) e[i].clear();for(int i=1;i<=n;i++) st[i].clear(); }int dep[N]; int fa[N][20];bool cmp(int a,int b) {return dfn[t[a]]<dfn[t[b]];} bool cmp2(int a,int b) {return dfn[t[a]]>dfn[t[b]];}int lca(int a,int b) {if(dep[a]<dep[b]) swap(a,b);for(int i=16;i>=0;i--)if(fa[a][i]&&dep[fa[a][i]]>=dep[b])a=fa[a][i];if(a==b) return a;for(int i=16;i>=0;i--)if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];return fa[a][0]; }void dfs(int v) {dfn[v]=++id;for(int i=1;i<=16;i++) fa[v][i]=fa[fa[v][i-1]][i-1];for(int i=0;i<e[v].size();i++) {int to=e[v][i];dep[to]=dep[v]+1;fa[to][0]=v;dfs(to);} }void build() {for(int i=1;i<=n;i++) {sort(st[i].begin(),st[i].end(),cmp);for(int j=0;j<st[i].size()-1;j++) {add(st[i][j],st[i][j+1],0);add(st[i][j]+tot,st[i][j+1]+tot,0);add(st[i][j],st[i][j+1]+tot,dep[lca(t[st[i][j]],t[st[i][j+1]])]);}reverse(st[i].begin(),st[i].end());for(int j=0;j<st[i].size()-1;j++) {add(st[i][j]+TOT,st[i][j+1]+TOT,0);add(st[i][j]+tot+TOT,st[i][j+1]+tot+TOT,0);add(st[i][j]+TOT,st[i][j+1]+tot+TOT,dep[lca(t[st[i][j]],t[st[i][j+1]])]);}} }struct node {int v,d;node() {v=0,d=0;}node(int a,int b) {v=a,d=b;}bool operator <(const node &a)const {return d>a.d;} }; priority_queue<node>q;bool vis[N]; void dij() {memset(vis,0,sizeof(vis));while(!q.empty()) {node tem=q.top();q.pop();int v=tem.v;if(vis[v]) continue ;vis[v]=1;for(int i=h[v];i;i=s[i].next) {int to=s[i].to;if(vis[to]) continue ;if(dis[to]>dis[v]+s[i].c) {dis[to]=dis[v]+s[i].c;q.push(node(to,dis[to]));}}} }int main() {int T=Get();while(T--) {n=Get(),m=Get(),k=Get();Init();tot=m<<1,TOT=tot<<1;int a,b,c,d;for(int i=1;i<=m;i++) {a=Get(),b=Get(),c=Get(),d=Get();t[i]=t[i+m]=d;w[i]=w[i+TOT]=c;st[b].push_back(i);st[a].push_back(i+m);add(i+m+tot,i,w[i]);add(i+m+tot+TOT,i,w[i]);add(i+m+tot,i+TOT,w[i]);add(i+m+tot+TOT,i+TOT,w[i]);}for(int i=1;i<k;i++) {a=Get(),b=Get(),c=Get();e[a].push_back(b);}dfs(1);build();for(int i=0;i<st[1].size();i++) {if(st[1][i]>m) {dis[st[1][i]-m]=dis[st[1][i]-m+TOT]=w[st[1][i]-m];q.push(node(st[1][i]-m,w[st[1][i]-m]));q.push(node(st[1][i]-m+TOT,w[st[1][i]-m]));}}dij();memset(ans,0x3f,sizeof(ans));for(int i=1;i<=n;i++) {for(int j=0;j<st[i].size();j++)if(st[i][j]<=m) {ans[i]=min(ans[i],min(dis[st[i][j]],dis[st[i][j]+TOT]));}}for(int i=2;i<=n;i++) cout<<ans[i]<<"\n";}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/hchhch233/p/10468062.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的【SDOI2017】天才黑客的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。