#6622. 「THUPC 2019」找树 / findtree

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

定义 \otimes_1, \otimes_2, \otimes_3 分别为按位与、按位或、按位异或运算。记 a_i 表示 a 的从低位到高位的第 i 个二进制位。定义一个作用在 w 位二进制数上的新运算 \oplus ,满足对于结果 a\oplus b 的每一位 (a\oplus b)_i (a\oplus b)_i = a_i \otimes_{\large o_i} b_i 。不难验证 \oplus 运算满足结合律和交换律。

给出一张 n 个点 m 条边的无向图,每一条边的权值是一个 w 位二进制数(即小于 2^w 的非负整数)。请你找一棵原图的生成树。设你找出的生成树中的边边权分别为 v_1,\cdots,v_{n-1} ,请你最大化 v_1\oplus v_2\oplus\cdots\oplus v_{n-1}

输入格式

第一行两个正整数 n,m

第二行一个长度为 w 的串,串中的每个字符为 &|^ 中的一个(分别代表与、或和异或),表示每一个 \otimes_{\large o_i}

接下来 m 行,每一行三个非负整数 x,y,v ,表示一条连接 x y 权值为 v 的边,保证 1\leq x,y\leq n 0\le v < 2^w

对于所有数据, 1\le n\le 70,1\le m\le 5000,1\le w \le 12

输出格式

输出一行一个数,表示答案。如果图不连通,输出 -1

样例

样例输入 1
3 3
^
1 2 1
2 3 1
1 3 0
样例输出 1
1

数据范围与提示

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。