首先可以证明 一条从起点到终点的路径可以拆成一条从起点到终点的简单路径+一些环
只要是在图上的环 都可以选择取或不取
因为可以走到某个点 绕环一圈 然后回到起点
这样的话 就只要对每个环进行消元(求基?线性无关?什么什么的= =
然后随便找一条从起点到终点的简单路径(可以证明随便找一条都可以
在那个求出来的数组里贪心的消一消 遇0就消 然后就是答案
具体做法可以dfs 无向图的dfs树只有返祖边 一条返祖边对应一个环
每个点记录dfs树上根到这个点xor和即可
环的权=sum[now] ^ sum[to] ^ v[now][to]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <string> #include <queue> #include <stack> #include <cmath> #include <map> #include <vector> #include <functional> #include <ctime> #include <cstdlib> #include <sstream> #include <set> #include <deque> using namespace std; typedef long long ll; typedef long double ld; const ll maxn = 50006; struct line { ll to, next, v; }li[maxn * 4]; ll be[maxn], n, m, t[105], d[maxn], l, b[maxn]; void makeline(ll fr, ll to, ll v) { ++l; li[l].next = be[fr]; be[fr] = l; li[l].to = to; li[l].v = v; } void add(ll v) { for (ll i = 61; i >= 0; --i) if (v & (1LL << i)) v ^= t[i]; for (ll i = 61; i >= 0; --i) if (v & (1LL << i)) { t[i] = v; break; } } void dfs(ll now) { for (ll i = be[now]; i; i = li[i].next) { ll to = li[i].to; if (b[to]) add(d[now] ^ d[to] ^ li[i].v); else { d[to] = d[now] ^ li[i].v; b[to] = 1; dfs(to); } } } int main() { freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); scanf("%lld%lld", &n, &m); for (ll i = 0; i < m; ++i) { ll fr, to, v; scanf("%lld%lld%lld", &fr, &to, &v); makeline(fr, to, v); makeline(to, fr, v); } b[1] = 1; dfs(1); for (ll i = 61; i >= 0; --i) if (!(d[n] & (1LL << i))) d[n] ^= t[i]; cout << d[n]; fclose(stdin);fclose(stdout); } |