广搜好啊
2024-06-18 15:30:31
发布于:上海
12阅读
0回复
0点赞
首先,先想简单的情况。
假如告诉你 ,已知 和 ,怎么求 ?
别忘了异或的性质:。
等式两边同时异或 :
。
那么现在就很简单了。把这些信息抽象成一张有权无向图,然后从点 开始拓展节点,用我们推的式子求出每一个点的值,没有遍历到的点当然就无法推出。构图,广搜应该都会吧。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <memory.h>
#include <vector>
#include <queue>
using namespace std;
struct edge{
int v,w;
};
vector<edge>e[100005];
int vis[100005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1; i<=m; i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
queue<int>q;
q.push(1);
memset(vis,-1,sizeof(vis));
vis[1]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0; i<e[u].size(); i++){
if(vis[e[u][i].v]==-1){
vis[e[u][i].v]=vis[u]^e[u][i].w;
q.push(e[u][i].v);
}
}
}
for(int i=1; i<=n; i++) cout<<vis[i]<<" ";
return 0;
}
这里空空如也
有帮助,赞一个