网站关键词更改,网址搜索ip地址,动漫网站在线免费观看,有手机网站了还要微网站吗BZOJ2115 Xor
题目描述#xff1a; 题目大意#xff1a;
给定一张 n 个点 m 条边的无向带权连通图#xff0c;求一条从点 1 到点 n 的路径#xff0c;使得经过的边权异或和最大。
路径可以经过重复点和重复边#xff0c;当一条边被重复经过时也会相应地被 xor 多次。 s…BZOJ2115 Xor
题目描述 题目大意
给定一张 n 个点 m 条边的无向带权连通图求一条从点 1 到点 n 的路径使得经过的边权异或和最大。
路径可以经过重复点和重复边当一条边被重复经过时也会相应地被 xor 多次。 solution
显然然而我不会严格证明QAQ答案是由一条 1 到 n 的路径和若干基本环构成的。
先做一个 序此处定义所有由 中儿子连向父亲的边称为返祖边。
则每一条返祖边会产生一个基本环。
先选择一条1-n的路径再从所有基本环里选择若干凑出最大异或和即可。
显然可以用线性基维护所有基本环的值。
So easy
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int MAXN200005;
struct enode{int to; ll c;};
bool vis[MAXN];
int num0,n,m;
ll s[MAXN],g[MAXN];
vectorenode e[MAXN];
ll read()
{ll f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)c-0; cgetchar(); }return x*f;
}
void dfs(int x,int father)
{//coutx s[x]endl;vis[x]1;for (int i0;ie[x].size();i)if (!vis[e[x][i].to]) {s[e[x][i].to]s[x]^e[x][i].c;dfs(e[x][i].to,x);}else if (e[x][i].to!father) g[num]s[x]^s[e[x][i].to]^e[x][i].c;
}
struct Xor_Basis
{int maxsz;ll basis[65];void init(){ memset(basis,0,sizeof basis); maxsz63; }bool insert(ll x){for (int imaxsz;i0;i--) if ((xi)1)if (basis[i]) x^basis[i];else { basis[i]x; break; }return x; }
} QAQ;
int main()
{QAQ.init();nread(),mread();for (int i1;im;i){int uread(),vread();ll cread();e[u].push_back((enode){v,c});e[v].push_back((enode){u,c});}dfs(1,0);for (int i1;inum;i) QAQ.insert(g[i]);ll anss[n];for (int iQAQ.maxsz;i0;i--) if (!((ansi)1)) ans^QAQ.basis[i];printf(%lld\n,ans);return 0;
}
代码较丑不喜勿喷。
