编程介的小学生 2016-10-24 03:00 采纳率: 19.7%
浏览 906
已采纳

计算最长的异或路径,请看下这个程序怎么修改

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 100005;

int n;
struct Edge {
int v, w, nex;
Edge() {}
Edge(int v, int w, int nex) : v(v), w(w), nex(nex) {}
};
Edge e[N << 1];
int head[N], tot;
void add(int u, int v, int w) {
e[tot] = Edge(v, w, head[u]);
head[u] = tot++;
}
void read() {
memset(head, -1, sizeof head);
tot = 0;
int u, v, w;
for(int i = 1; i < n; ++i) {
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
}
int d[N], vis[N];
void bfs() {
queue que;
que.push(0);
d[0] = 0;
memset(vis, 0, sizeof vis);
int u, v, w;
vis[0] = 1;
while(!que.empty()) {
u = que.front(); que.pop();
for(int i = head[u]; ~i; i = e[i].nex) {
v = e[i].v; w = e[i].w;
if(vis[v]) continue;
d[v] = d[u] ^ w;
vis[v] = 1;
que.push(v);
}
}
}
int ch[N * 32][2];
struct Trie {
int sz;
Trie() { sz = 1; memset(ch[0], 0, sizeof ch[0]); }
void _insert(int bs[]) {
int u = 0;
for(int i = 30; i >= 0; --i) {
int c = bs[i];
if(!ch[u][c]) {
memset(ch[sz], 0, sizeof ch[sz]);
ch[u][c] = sz++;
}
u = ch[u][c];
}
}
int _search(int bs[]) {
int u = 0, ans = 0;
for(int i = 30; i >= 0; --i) {
int c = bs[i];
if(c == 1) {
if(ch[u][0]) { ans += (1 << (i)); u = ch[u][0]; }
else u = ch[u][1];
}else {
if(ch[u][1]) { ans += (1 << (i)); u = ch[u][1]; }
else u = ch[u][0];
}
}
return ans;
}
};

int ans;
int b[35];
void get(int x) {
int ls = 0;
memset(b, 0, sizeof b);
while(x) {
b[ls++] = x % 2;
x >>= 1;
}
}
void solve() {
Trie mytrie;
ans = 0;
for(int i = 0; i < n; ++i) {
get(d[i]);
mytrie._insert(b);
ans = max(ans, mytrie._search(b));
}
printf("%d\n", ans);
}
int main() {
// freopen("in.txt", "r", stdin);
while(~scanf("%d", &n)) {
read();
bfs();
solve();
}
}

  • 写回答

1条回答 默认 最新

  • threenewbee 2016-10-24 02:59
    关注

    你用的什么编译器,不是所有的编译器都支持long long
    用GCC 14看看

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥20 qt中connect两个signal
  • ¥20 pix2pixHD运行测试命令时出现数据类型错误无法反向传播的问题
  • ¥15 python处理Excel符合条件的行自动填写数据分类
  • ¥15 汇编hook举例并讲解(通俗易懂,学习用)
  • ¥20 用c++语言模拟键盘电子琴设计
  • ¥15 STM32cubemx生成keil工程,有问题与正常的情况不同,求解!
  • ¥15 如何自动点击银行app的安全键盘,实现密码自动输入
  • ¥15 关于四边形重叠的问题
  • ¥15 用verilog语言设计一个简易的八音符电子琴,可通过按键输入来控制音响。演奏时可以选择是手演奏(由键盘输入)或自动演奏已存入的乐曲。能够自动演奏多首乐曲,且每首乐曲可重复演奏
  • ¥15 sap gui脚本每次到导出Excel的时候就停住不动。不会另存为。