Description
渐渐地,Magic Land上的人们对那座岛屿上的各种现象有了深入的了解。
为了分析一种奇特的称为梦想封印(Fantasy Seal)的特技,需要引入如下的概念:
每一位魔法的使用者都有一个“魔法脉络”,它决定了可以使用的魔法的种类。
一般地,一个“魔法脉络”可以看作一个无向图,有N个结点及M条边,将结点编号为1~N,其中有一个结点是特殊的,称为核心(Kernel),记作1号结点。每一条边有一个固有(即生成之后再也不会发生变化的)权值,是一个不超过U的自然数。
每一次魔法驱动,可看作是由核心(Kernel)出发的一条有限长的道路(Walk),可以经过一条边多次,所驱动的魔法类型由以下方式给出:
将经过的每一条边的权值异或(xor)起来,得到s。
如果s是0,则驱动失败,否则将驱动编号为s的魔法(每一个正整数编号对应了唯一一个魔法)。
需要注意的是,如果经过了一条边多次,则每一次都要计入s中。
这样,魔法脉络决定了可使用魔法的类型,当然,由于魔法与其编号之间的关系尚未得到很好的认知,此时人们仅仅关注可使用魔法的种类数。
梦想封印可以看作是对“魔法脉络”的破坏:
该特技作用的结果是,“魔法脉络”中的一些边逐次地消失。
我们记总共消失了Q条边,按顺序依次为Dis1、Dis2、……、DisQ。
给定了以上信息,你要计算的是梦想封印作用过程中的效果,这可以用Q+1个自然数来描述:
Ans0为初始时可以使用魔法的数量。
Ans1为Dis1被破坏(即边被删去)后可以使用魔法的数量。
Ans2为Dis1及Dis2均被破坏后可使用魔法的数量。
……
AnsQ为Dis1、Dis2、……、DisQ全部被破坏后可以使用魔法的数量。
Input
第一行包含三个正整数N、M、Q。
接下来的M行,每行包含3个整数,Ai、Bi、Wi,表示一条权为Wi的与结点Ai、Bi关联的无向边,其中Wi是不超过U的自然数。
接下来Q行,每行一个整数:Disi。
Output
一共包Q+1行,依次为Ans0、Ans1、……、AnsQ。
Sample Input
Sample Output
HINT
【数据规模和约定】
所有数据保证该无向图不含重边、自环。所有数据保证不会有一条边被删除多次,即对于不同i和j,有Disi≠Disj
30%的数据中N ≤ 50,M ≤ 50,Q ≤50,U≤100;
60%的数据中N ≤ 300,M ≤ 300,Q ≤50,U≤10^9;
80%的数据中N ≤ 300,M ≤ 5000,Q ≤5000,U≤10^18;
100%的数据中N ≤ 5000,M ≤ 20000,Q ≤20000,U≤10^18;
dwn(i,62,0) val=min(val,val^Q[i]);if(!val) return;cnt++;dwn(i,62,0) if(val>>i&1) {Q[i]=val;break;}
最多有logN个线性基是有效的(即重构路径集合),且set维护集合与消元过程均为O(logN),所以总时间复杂度为O(MlogN)。
#include#include #include #include #include #define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define ren for(int i=first[x];i!=-1;i=edges[i].next)using namespace std;const int BufferSize=1<<16;char buffer[BufferSize],*head,*tail;inline char Getchar() { if(head==tail) { int l=fread(buffer,1,BufferSize,stdin); tail=(head=buffer)+l; } return *head++;}typedef long long ll;inline ll read() { ll x=0,f=1;char c=Getchar(); for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1; for(;isdigit(c);c=Getchar()) x=x*10+c-'0'; return x*f;}const int maxn=5010;const int maxm=20010;set S;ll Q[65],tmp[maxn],ans[maxm],A[maxn],w[maxm];int n,m,q,e,cnt,vis[maxn],first[maxn],num[maxm],del[maxm],u[maxm],v[maxm];struct Edge {int u,v,next;ll w;}edges[maxm<<1];void AddEdge(int from,int to,ll dis) { edges[e]=(Edge){from,to,first[from],dis};first[from]=e++; edges[e]=(Edge){to,from,first[to],dis};first[to]=e++;}void gauss(ll val) { dwn(i,62,0) val=min(val,val^Q[i]); if(!val) return;cnt++; dwn(i,62,0) if(val>>i&1) {Q[i]=val;break;} int top=0; for(set ::iterator it=S.begin();it!=S.end();it++) tmp[++top]=*it; S.clear(); rep(i,1,top) S.insert(min(tmp[i],tmp[i]^val));}void dfs(int x,int last) { vis[x]=1;A[x]=A[edges[last].u]^edges[last].w; ll val=A[x]; dwn(i,62,0) val=min(val,val^Q[i]); S.insert(val); ren { Edge& e=edges[i]; if(i==(last^1)) continue; if(!vis[e.v]) dfs(e.v,i); else gauss(A[e.v]^A[x]^e.w); }}void Add(int k) { int x=u[k],y=v[k];AddEdge(x,y,w[k]); if(vis[x]&&vis[y]) gauss(w[k]^A[x]^A[y]); else if(vis[x]) dfs(y,e-2); else if(vis[y]) dfs(x,e-1);}int main() { memset(first,-1,sizeof(first)); n=read();m=read();q=read(); rep(i,1,m) u[i]=read(),v[i]=read(),w[i]=read(); rep(i,1,q) del[num[i]=read()]=1; vis[1]=1;S.insert(0); rep(i,1,m) if(!del[i]) Add(i); dwn(i,q,1) { ans[i]=S.size()*(1ll<