Studying Father's luogu blog

Studying Father's luogu blog

从零至灵,由壹达意

题解 P5651 【基础最短路练习题】

posted on 2019-11-13 18:57:54 | under 题解 |

一道非常棒的思维题。

首先考虑没有环的情况,这时候我们随便取一个点作为根节点进行 DFS,求出每个点 $i$ 到根节点路径的权值 $dis_i$ 。

这时候 $u$ 到 $v$ 路径的权值显然为 $dis_u \oplus dis_v$ 。

接下来考虑有环的情况。

题目中给的图性质非常特殊:保证 $G$ 中不存在简单环使得边权异或和不为 $0$ ,也即所有环的权值均为零。

这意味着,如果我们把一个环分割为两段,这两段的权值相等(否则环的权值就不为 $0$ 了)。

因此假如从 $u$ 到 $v$ 的路径经过了一个环,我们只需保留环的其中一段即可(另外一段和这一段是一样的)。

这样,我们求出图的任意一个生成树,就可以把问题转化为树的情况。

到此,问题得到了完美解决。

#include <cstdio>
struct edge
{
 int v,w,next;
}e[400005];
int fa[100005],head[100005],dis[100005],cnt;
void addedge(int u,int v,int w)
{
 e[++cnt].v=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
int find(int x)
{
 return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
 fa[y]=x;
}
void dfs(int u,int fa,int w)
{
 dis[u]=w;
 for(int i=head[u];i;i=e[i].next)
  if(e[i].v!=fa)
   dfs(e[i].v,u,w^e[i].w);
}
int main()
{
 int n,m,q;
 scanf("%d%d%d",&n,&m,&q);
 for(int i=1;i<=n;i++)
  fa[i]=i;
 for(int i=1;i<=m;i++)
 {
  int u,v,w;
  scanf("%d%d%d",&u,&v,&w);
  int fu=find(u),fv=find(v);
  if(fu!=fv)
  {
   unionn(fu,fv);
   addedge(u,v,w);
   addedge(v,u,w);
  }
 }
 dfs(1,0,0);
 while(q--)
 {
  int u,v;
  scanf("%d%d",&u,&v);
  printf("%d\n",dis[u]^dis[v]);
 }
 return 0;
}