题解 P5651 【基础最短路练习题】
StudyingFather
2019-11-13 18:57:54
一道非常棒的思维题。
首先考虑没有环的情况，这时候我们随便取一个点作为根节点进行 DFS，求出每个点 $i$ 到根节点路径的权值 $dis_i$。
这时候 $u$ 到 $v$ 路径的权值显然为 $dis_u \oplus dis_v$。
接下来考虑有环的情况。
题目中给的图性质非常特殊：保证 $G$ 中不存在简单环使得边权异或和不为 $0$，也即所有环的权值均为零。
这意味着，如果我们把一个环分割为两段，这两段的权值相等（否则环的权值就不为 $0$ 了）。
因此假如从 $u$ 到 $v$ 的路径经过了一个环，我们只需保留环的其中一段即可（另外一段和这一段是一样的）。
这样，我们求出图的任意一个生成树，就可以把问题转化为树的情况。
到此，问题得到了完美解决。
```cpp
#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;
}
```