problem
连通图,无自环,无重边,\(m-n\leq 20\),\(n\leq 10^5\),\(10^5\) 询问两点之间最短路。
solution
搞出任意一棵生成树。一共 \(21\) 条非树边。
对于任意一条路径,它只有如下 \(22\) 种情况:
- 不经过非树边。
- 经过第 \(i\) 条非树边(\(1\leq i\leq 21\))。
这里我们不用枚举非树边的子集之类的东西,一是不好做,二是这是最优性问题,每个元素的方案的并就是全集。
对于不经过非树边的,【模板】树上两点带权距离。
对于经过一条非树边的,从边的一端开始跑最短路即可。
最后的答案为以上 \(22\) 种情况的 \(\min\)。复杂度 \(O(mk\log m+q(\log n+k))\) 其中 \(k=m-n\)。
code
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template<int N> struct dsu{
int fa[N+10],siz[N+10],cnt;
dsu(int n=N):cnt(n){for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){if(x=find(x),y=find(y),x!=y) cnt--,siz[x]<siz[y]&&(swap(x,y),0),siz[fa[y]=x]+=siz[y];}
};
template<int N,int M,class T=int> struct graph{
int head[N+10],nxt[M*2+10],cnt;
struct edge{
int u,v;T w;
edge(int u=0,int v=0,T w=0):u(u),v(v),w(w){}
} e[M*2+10];
graph(){memset(head,cnt=0,sizeof head);}
edge&operator[](int i){return e[i];}
int add(int u,int v,T w=0){return e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
int link(int u,int v,T w=0){return add(u,v,w),add(v,u,w);}
};
template<int N,int M,class T=int> struct shortway: public graph<N,M,T>{
graph<N,M,T> &g=*this;
bool vis[N+10];
void dijkstra(int s,LL dis[]){
memset(vis,0,sizeof vis);
priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>> q;
for(q.push({dis[s]=0,s});!q.empty();){
int u=q.top().second; q.pop();
if(vis[u]) continue; else vis[u]=1;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(dis[v]>dis[u]+g[i].w) q.push({dis[v]=dis[u]+g[i].w,v});
}
}
}
};
template<int N,int M,class T=int> struct treecut: public graph<N,M,T>{
graph<N,M,T> &g=*this;
int fa[N+10],dep[N+10],son[N+10],siz[N+10],
dfn[N+10],rnk[N+10],top[N+10],cnt;
treecut(){memset(son,cnt=siz[0]=0,sizeof son);}
void dfs(int u,int f=0){
dep[u]=dep[fa[u]=f]+1,siz[u]=1;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v; if(v==fa[u]) continue;
dfs(v,u),siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void cut(int u,int topf){
top[rnk[dfn[u]=++cnt]=u]=topf;
if(son[u]) cut(son[u],topf);
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v; if(v==fa[u]||v==son[u]) continue;
cut(v,v);
}
}
int lca(int u,int v){
for(;top[u]!=top[v];u=fa[top[u]]) if(dep[top[u]]<dep[top[v]]) swap(u,v);
if(dep[u]<dep[v]) swap(u,v); return v;
}
};
int n,m,q,pos[30],cnt;
LL dis[30][100010],sum[100010];
shortway<100010,100100> g;
treecut<100010,100010> t;
dsu<100010> s;
void dfs(int u){for(int i=t.head[u];i;i=t.nxt[i]) if(t[i].v!=t.fa[u]) sum[g[i].v]=sum[u]+g[i].w,dfs(t[i].v);}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
pos[++cnt]=g.link(u,v,w);
if(s.find(u)!=s.find(v)) cnt--,t.link(u,v,w),s.merge(u,v);
}
memset(dis,0x3f,sizeof dis);
for(int i=1;i<=cnt;i++) g.dijkstra(g[pos[i]].u,dis[i]);
t.dfs(1),t.cut(1,1),dfs(1);
scanf("%d",&q);
for(int i=1,u,v;i<=q;i++){
scanf("%d%d",&u,&v);
LL ans=sum[u]+sum[v]-2*sum[t.lca(u,v)];
for(int j=1;j<=cnt;j++) ans=min(ans,dis[j][u]+dis[j][v]);
printf("%lld\n",ans);
}
return 0;
}
标签:10,cnt,int,题解,head,graph,Statement,siz,Shortest
From: https://www.cnblogs.com/caijianhong/p/solution-CF1051F.html