BZOJ 2322 BeiJing2011 夢想封印 高斯消元

BZOJ 2322 BeiJing2011 夢想封印 高斯消元

題目大意：給定一張帶權無向圖，每次刪去一條邊並詢問從點1出發走一條路徑可以走出多少種不同的邊權異或和

刪邊不好做 首先倒著做 把刪邊改成加邊

回憶2115那題的做法 我們可以把一條路徑的異或和拆成一條簡單路徑和一些環的異或值

2115是求最大異或和 這個題是求異或和的個數

因此我們維護兩個集合 環的異或和集合和路徑的異或和集合

這裡說的路徑包括原地不動 即從1到1的路徑

如果一個環的異或和能被其它環線性表示 那麼這個環對答案顯然沒有貢獻 於是這個環就可以從集合中刪掉

因此環的集合要維護一個線性基的形式

如果一條路徑的異或和異或上一些環之後等於另一條路徑，這條路徑對答案顯然沒有貢獻

因此路徑的集合需要對線性基消元，且保證消元後不重

設環的集合大小為R，路徑的集合大小為P，那麼答案就是P*2^R-1

不過這題需要動態維護- - 實現起來就比較麻煩了- - 我細說吧- -

首先思想是維護一棵以1為根的生成樹，將樹上的路徑都視作路徑，每條非樹邊對應一個環

路徑集合的去重利用set來完成

每添加一條邊，步驟如下：

如果邊的兩端點都被訪問過，就把這條邊所在環的異或值扔進線性基中消元

如果此次消元後線性基被更新，那麼將set中所有的路徑取出，對本次更新的線性基消元後再放回去

如果只有一端點被訪問過，那麼就深搜另一端點所在聯通塊，標記訪問節點

對於深搜到的每個點，將1號節點到該節點的路徑的異或和對線性基消元後扔進set

對於深搜到的每條非樹邊，扔進線性基中消元並更新set中的元素

時間復雜度O(nlognlogk) 其中k是最大的邊權

#include 
#include 
#include 
#include 
#include 
#define M 20200
using namespace std;
struct edge{
	int x,y;
	long long z;
}edges[M];
struct abcd{
	int to,next;
	long long f;
}table[M<<1];
int head[M],tot=1;
int n,m,q,cnt;
bool _v[M],v[M];
int queries[M];
long long a[M],ans[M],linear_bases[64];
set s;
void Add(int x,int y,long long z)
{
	table[++tot].to=y;
	table[tot].f=z;
	table[tot].next=head[x];
	head[x]=tot;
}
void Gauss_Elimination(long long x)
{
	int i;
	for(i=62;~i;i--)
		if( (x^linear_bases[i])::iterator it;
	for(it=s.begin();it!=s.end();it++)
		stack[++top]=*it;
	for(s.clear();top;top--)
		s.insert( min(stack[top],stack[top]^x) );
}
void DFS(int x,int from)
{	
	int i;
	v[x]=1;
	a[x]=a[table[from^1].to]^table[from].f;
	long long temp=a[x];
	for(i=62;~i;i--)
		temp=min(temp,temp^linear_bases[i]);
	s.insert(temp);
	for(i=head[x];i;i=table[i].next)
		if(i^from^1)
		{
			if(!v[table[i].to])
				DFS(table[i].to,i);
			else
				Gauss_Elimination(table[i].f^a[x]^a[table[i].to]);
		}
}
void Insert(int id)
{
	int x=edges[id].x;
	int y=edges[id].y;
	Add(x,y,edges[id].z);
	Add(y,x,edges[id].z);
	if(v[x]&&v[y])www.Bkjia.com
		Gauss_Elimination(edges[id].z^a[x]^a[y]);
	else if(v[x])
		DFS(y,tot-1);
	else if(v[y])
		DFS(x,tot);
}
int main()
{
	int i,x,y;
	long long z;
	cin>>n>>m>>q;
	for(i=1;i<=m;i++)
	{
		#ifdef ONLINE_JUDGE
			scanf("%d%d%lld",&x,&y,&z);
		#else
			scanf("%d%d%I64d",&x,&y,&z);
		#endif
		edges[i].x=x;
		edges[i].y=y;
		edges[i].z=z;
	}
	for(i=1;i<=q;i++)
	{
		scanf("%d",&queries[i]);
		_v[queries[i]]=true;
	}
	s.insert(0);
	v[1]=1;
	for(i=1;i<=m;i++)
		if(!_v[i])
			Insert(i);
	for(i=q;i;i--)
	{
		ans[i]=s.size()*(1ll<