[BZOJ2322][BeiJing2011]梦想封印
试题描述
渐渐地, Magic Land 上的人们对那座岛屿上的各种现象有了深入的了解
为了分析一种奇特的称为梦想封印 (Fantasy Seal) 的特技, 需要引入如下的概念:
每一位魔法的使用者都有一个魔法脉络, 它决定了可以使用的魔法的种类
一般地, 一个魔法脉络可以看作一个无向图, 有 \(N\) 个结点及 \(M\) 条边, 将结点编号为 \(1 \sim N\), 其中有一个结点是特殊的, 称为核心 (Kernel), 记作 \(\underline 1\) 号结点每一条边有一个固有(即生成之后再也不会发生变化的) 权值, 是一个不超过 \(U\) 的自然数
每一次魔法驱动, 可看作是由核心 (Kernel) 出发的一条有限长的道路(Walk), 可以经过一条边多次, 所驱动的魔法类型由以下方式给出:
将经过的每一条边的权值异或 (xor) 起来, 得到 \(s\)
如果 \(\underline s\) 是 \(\underline 0\), 则驱动失败, 否则将驱动编号为 \(s\) 的魔法(每一个正整数编号对应了唯一一个魔法)
需要注意的是, 如果经过了一条边多次, 则每一次都要计入 \(\underline s\) 中
这样, 魔法脉络决定了可使用魔法的类型, 当然, 由于魔法与其编号之间的关系尚未得到很好的认知, 此时人们仅仅关注可使用魔法的种类数
梦想封印可以看作是对魔法脉络的破坏:
该特技作用的结果是, 魔法脉络中的一些边逐次地消失
我们记总共消失了 \(Q\) 条边, 按顺序依次为 \(Dis_1\)\(Dis_2\)\(Dis_Q\)
给定了以上信息, 你要计算的是梦想封印作用过程中的效果, 这可以用 \(Q+1\) 个自然数来描述:
\(Ans_0\) 为初始时可以使用魔法的数量
\(Ans_1\) 为 \(Dis_1\) 被破坏 (即边被删去) 后可以使用魔法的数量
\(Ans_2\) 为 \(Dis_1\) 及 \(Dis_2\) 均被破坏后可使用魔法的数量
\(Ans_Q\) 为 \(Dis_1\)\(Dis_2\)\(Dis_Q\)全部被破坏后可以使用魔法的数量
输入
第一行包含三个正整数 \(N\)\(M\)\(Q\)
接下来的 \(M\) 行, 每行包含 \(3\) 个整数,\(A_i\)\(B_i\)\(W_i\), 表示一条权为 \(W_i\) 的与结点 \(A_i\)\(B_i\) 关联的无向边, 其中 \(W_i\) 是不超过 \(U\) 的自然数
接下来 \(Q\) 行, 每行一个整数:\(Dis_i\)
输出
一共包 \(Q+1\) 行, 依次为 \(Ans_0\)\(Ans_1\)\(Ans_Q\)
输入示例 1
- 3 3 2
- 1 2 1
- 2 3 2
- 3 1 4
- 1
- 3
输出示例 1
5 2 0
输入示例 2
- 5 7 7
- 1 2 1
- 1 3 1
- 2 4 2
- 2 5 2
- 4 5 4
- 5 3 9
- 4 3 1
- 7
- 6
- 5
- 4
- 3
- 2
- 1
输出示例 2
15 11 5 2 2 1 1 0
数据规模及约定
\(30\%\) 的数据中 \(N \le 50\),\(M \le 50\),\(Q \le 50\),\(U \le 100\);
\(60\%\) 的数据中 \(N \le 300\),\(M \le 300\),\(Q \le 50\),\(U \le 10^9\);
\(80\%\) 的数据中 \(N \le 300\),\(M \le 5000\),\(Q \le 5000\),\(U \le 10^{18}\);
\(100\%\) 的数据中 \(N \le 5000\),\(M \le 20000\),\(Q \le 20000\),\(U \le 10^{18}\);
题解
一个合法的 \(s\) 是由与 \(1\) 处于同一个连通块中的随便多少个环与某一条从 \(1\) 出发的路径异或出来的
对所有和 \(1\) 在一起的环维护线性基, 用 dfs 树做, 每一条返祖边都是一个环, 路径就是 dfs 树上某个节点到根节点的路径开个 set 维护本质不同的路径(即和当前线性基能组合出的最小异或值不同的链才算本质不同)
这题是不断删边不好做, 我们考虑倒过来处理变成加边问题
如果加的边两端点都不和 \(1\) 在一起, 就直接在邻接表里加上边;
如果有且仅有一个端点和 \(1\) 在一起, 就相当与扩充连通块, 直接从另一个端点开始暴力 dfs, 扩大整个 dfs 树, 同时把多的环加进线性基;
如果两个端点都和 \(1\) 在一起, 就把新产生的环加入线性基即可
注意每次更新线性基时更新一下 set
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cctype>
- #include <algorithm>
- #include <set>
- #include <cassert>
- using namespace std;
- #define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
- #define dwn(i, s, t) for(int i = (s), mi = (t); i>= mi; i--)
- #define LL long long
- LL read() {
- LL x = 0, f = 1; char c = getchar();
- while(!isdigit(c)){ if(c == -) f = -1; c = getchar(); }
- while(isdigit(c)){ x = x * 10 + c - 0; c = getchar(); }
- return x * f;
- }
- #define maxn 5010
- #define maxm 40010
- #define maxlog 61
- #define pll pair <LL, LL>
- #define x first
- #define y second
- #define mp(x, y) make_pair(x, y)
- int n, m, q, M, siz, head[maxn], nxt[maxm], to[maxm], del[maxm];
- LL dist[maxm], A[maxlog], Ans[maxm];
- bool tag[maxm];
- set <LL> S;
- struct Edge {
- int a, b; LL c;
- Edge() {}
- Edge(int _1, int _2, LL _3): a(_1), b(_2), c(_3) {}
- } es[maxm];
- void AddEdge(int a, int b, LL c) {
- to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
- swap(a, b);
- to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
- return ;
- }
- LL f[maxn];
- bool vis[maxn];
- pll chg[maxn];
- LL Qry(LL x) {
- dwn(i, maxlog - 1, 0) x = min(x, x ^ A[i]);
- return x;
- }
- void UpdateSet() {
- int cc = 0;
- for(set <LL> :: iterator it = S.begin(); it != S.end(); it++) chg[++cc] = mp(*it, Qry(*it));
- S.clear();
- rep(i, 1, cc) if(!S.count(chg[i].y)) S.insert(chg[i].y);
- return ;
- }
- void Add(LL x) {
- dwn(i, maxlog - 1, 0) if(x>> i & 1) {
- if(A[i]) x ^= A[i];
- else{ A[i] = x; siz++; break; }
- }
- return UpdateSet();
- }
- void AddSet(LL x) {
- x = Qry(x);
- if(!S.count(x)) S.insert(x);
- return ;
- }
- void build(int u, int fa) {
- AddSet(f[u]);
- vis[u] = 1;
- for(int e = head[u]; e; e = nxt[e]) {
- if(vis[to[e]]) Add(f[u] ^ f[to[e]] ^ dist[e]);
- else f[to[e]] = f[u] ^ dist[e], build(to[e], u);
- }
- return ;
- }
- int main() {
- n = read(); M = read(); q = read();
- rep(i, 1, M) {
- int a = read(), b = read(); LL c = read();
- es[i] = Edge(a, b, c);
- }
- rep(i, 1, q) tag[del[i] = read()] = 1;
- rep(i, 1, M) if(!tag[i]) AddEdge(es[i].a, es[i].b, es[i].c);
- build(1, 0);
- Ans[q+1] = (LL)S.size() * (1ll << siz) - 1;
- dwn(i, q, 1) {
- int a = es[del[i]].a, b = es[del[i]].b; LL c = es[del[i]].c;
- AddEdge(a, b, c);
- if(vis[a] && vis[b]) Add(f[a] ^ f[b] ^ c);
- else if(vis[a]) f[b] = f[a] ^ c, build(b, a);
- else if(vis[b]) f[a] = f[b] ^ c, build(a, b);
- Ans[i] = (LL)S.size() * (1ll << siz) - 1;
- }
- rep(i, 1, q + 1) printf("%lld\n", Ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2525204.html