支配树学习
利用bfs和lca巧妙的求出DAG上的直接支配点
存储的时候注意
第一张图：正向建图
第二张图：反向建图
第三张图：重构后图（树）
再设虚拟根节点0，连接所有DAG度为0的点
核心环节：利用lca重构树，类似并查集，（第三张图有时可省略）
#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxn (100000+10)
#define maxm (3000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int head1[maxn],pre1[maxm],tot1,to1[maxm];
int head2[maxn],pre2[maxm],tot2,to2[maxm];
int head[maxn],pre[maxm],tot,to[maxm];
int n,in[maxn];
int dep[maxn],p[maxn],f[maxn][30];
int sz[maxn];
queue<int>Q;
void a(int u,int v)
{
to[++tot]=v,pre[tot]=head[u],head[u]=tot;
}
void a1(int u,int v)
{
to1[++tot1]=v,pre1[tot1]=head1[u],head1[u]=tot1;
}
void a2(int u,int v)
{
to2[++tot2]=v,pre2[tot2]=head2[u],head2[u]=tot2;
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])
x=f[x][i];
if(x==y)return x;
//for(int i=0;i<2;i++)see(x),see(y),see(i),see(f[x][i]),see(f[y][i]),NL;
for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i])
//see(i),see(x),see(y),see(dep[x]),see(dep[y]),see(f[x][i]),see(f[y][i]),NL,
x=f[x][i],y=f[y][i];
return f[x][0];
}
void bfs()
{
NEG(p);p[0]=0;for(int i=1;i<=n;i++)if(!in[i])
{
Q.push(i);p[i]=0;dep[i]=1;
}
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=head2[u];i;i=pre2[i])
{
int v=to2[i];in[v]--;
if(!in[v])Q.push(v);
}
for(int i=head1[u];i;i=pre1[i])
{
int v=to1[i];
if(p[u]==-1)p[u]=v;
else p[u]=lca(p[u],v);
}
dep[u]=dep[p[u]]+1;
f[u][0]=p[u];
for(int i=1;i<=20;i++)
f[u][i]=f[f[u][i-1]][i-1];
a(u,p[u]),a(p[u],u);
}
}
void dfs(int u,int from)
{
sz[u]=1;
for(int i=head[u];i;i=pre[i])
{
int v=to[i];if(v==from)continue;
dfs(v,u);sz[u]+=sz[v];
}
}
int main()
{
//fi;
RD1(n);for(int i=1;i<=n;i++)
{
int t;while(RD1(t)&&t)
{//see(t);
a1(i,t),a2(t,i);in[i]++;
}
}
bfs();
dfs(0,-1);
for(int i=1;i<=n;i++)printf("%d\n",sz[i]-1);
return 0;
} 圆方树学习
圆方树的本质就是去掉环，重构出’等效‘的图
去掉环时保证距离是等效的就行
首先建出仙人掌圆方树（与点双圆方树的区别在于直接连割边，也就是存在圆圆边），然后考虑点u-v的最短路径，显然就是：在圆方树上u-v的路径上的所有边权之和，加上每个环（方点）中连出去的两个点的最短距离。
现在问题就是：如何求出环上两个点的最短路径。考虑这样设定边权，首先显然圆圆边的边权就是原图的边权，然后设一个环在搜索树中深度最小的点为这个环的根，则方圆边的边权是环的根到这个点的最短距离，这个可以在Tarjan的时候直接求出。
但是圆方树问题通常需要在LCA处分圆方点讨论。首先如果LCA是圆点，那么直接做即可。如果是方点，就需要决定要不要走环的另一侧，这个同样直接讨论即可。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std;
const int N=20010;
int n,m,Q,u,v,w,tot,tim,top,dep[N],len[N],type[N],stk[N];
int dfn[N],low[N],dis[N],lst[N],fa[N][16],sm[N][16];
//dis 维护搜索树根节点到每个节点的距离
//lst 维护一个节点上一次被访问时，到达该节点的边的长度
struct E{
int cnt,h[N],to[N<<1],nxt[N<<1],val[N<<1];
void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; }
}G,G1;
void work(int x,int k){
tot++; int t; len[tot]=dis[stk[top]]-dis[x]+lst[stk[top]];//环上最早被访问的元素作为环的根，环的总长=dis[环上最后被访问的元素]-dis[根]+lst[根]
do{
t=stk[top--];
int A=dis[t]-dis[x],B=len[tot]-A;
G1.add(tot,t,min(A,B)); type[t]=(A<=B);
}while (t!=k);
G1.add(x,tot,0);
}
void Tarjan(int x,int pre){
//printf("%d\n",x);
dfn[x]=low[x]=++tim; stk[++top]=x;
for (int i=G.h[x],k; i; i=G.nxt[i]){
if ((k=G.to[i])==pre) continue;
if (!dfn[k]){
dis[k]=dis[x]+G.val[i]; Tarjan(k,x);
//printf("%d %d %d %d\n",x,k,dfn[x],low[k]);
if (low[k]>dfn[x]) top--,G1.add(x,k,G.val[i]);//提前弹出不和x一个环的节点
else if (low[k]==dfn[x]) work(x,k);//为什么可以直接弹出整个连通分量？因为仙人掌保证环和环之间没有公共边，一个环只会进栈一次，所以提前出栈
low[x]=min(low[x],low[k]);
}else low[x]=min(low[x],dfn[k]),lst[x]=G.val[i];
}
}
void dfs(int x,int pre){
for (int i=G1.h[x],k; i; i=G1.nxt[i])
fa[k=G1.to[i]][0]=x,dep[k]=dep[x]+1,sm[k][0]=G1.val[i],dfs(k,x);
}
int lca(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
int t=dep[u]-dep[v],res=0;
for (int i=15; ~i; i--) if (t&(1<<i)) res+=sm[u][i],u=fa[u][i];
if (u==v) return res;
for (int i=15; ~i; i--) if (fa[u][i]!=fa[v][i])
res+=sm[u][i]+sm[v][i],u=fa[u][i],v=fa[v][i];
if (fa[u][0]<=n) return sm[u][0]+sm[v][0]+res;
int A=sm[u][0],B=sm[v][0],mn;
if (type[u]==type[v]) mn=min(abs(A-B),len[fa[u][0]]-abs(A-B));
else mn=min(A+B,len[fa[u][0]]-A-B);
return res+mn;
}
int main(){
freopen("bzoj2125.in","r",stdin);
freopen("bzoj2125.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q); tot=n;
rep(i,1,m) scanf("%d%d%d",&u,&v,&w),G.add(u,v,w),G.add(v,u,w);
Tarjan(1,0); dfs(1,0);
//rep(i,1,tot) printf("%d ",low[i]); puts("");
rep(j,1,15) rep(i,1,tot)
fa[i][j]=fa[fa[i][j-1]][j-1],sm[i][j]=sm[i][j-1]+sm[fa[i][j-1]][j-1];
rep(i,1,Q) scanf("%d%d",&u,&v),printf("%d\n",lca(u,v));
return 0;
} 
京公网安备 11010502036488号