「ZJOI2014」璀灿光华

实际上，可以不用建水晶立方体...

因为，发光水晶的方向都要枚举一遍。

只需知道发光水晶每个方向有哪些水晶就可以了。

对于一个发光水晶，将它连接的水晶标号。

从该水晶bfs，若某水晶在相同步数下被访问过两次，那么它必然不是某一方向的直线上的（挺显然的吧）。

每个点的标号为最先访问到它的点的标号。

这样可以整出发光水晶每个方向的水晶。

时间复杂度\(o(n a^3)\)。

之后把每个发光水晶朝向枚举一遍，复杂度\(o(6^n a)\)。

#include<bits/stdc++.h>

#define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)

#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)

#define mem(a,b) memset(a,b,sizeof a )

#define debug(a) cerr<<#a<<' '<<a<<"___"<<endl

using namespace std;

void in(int &r) {

	static char c;

	r=0;

	while(c=getchar(),c<48);

	do r=(r<<1)+(r<<3)+(c^48);

	while(c=getchar(),c>47);

}

const int mn=70*70*70+100;

int n;

vector<int> son[mn];

vector<int> rt,ft[8][6];

int mk[mn];

int val[mn],que[mn],mark[mn];

bool is_used[mn];

int tot_val,Max,Min=1e9;

void dfs(int x){

	if(x==(int)rt.size()){

		Max=max(Max,tot_val);

		Min=min(Min,tot_val);

		return;

	}

	vector<int> sta;

	rep(q,0,5){

		sta.clear();

		rep(w,0,(int)ft[x][q].size()-1){

			int y=ft[x][q][w];

			if(!is_used[y]){

				sta.push_back(y);

				is_used[y]=1;

				tot_val+=val[y];

			}

		}

		dfs(x+1);

		rep(w,0,(int)sta.size()-1)is_used[sta[w]]=0,tot_val-=val[sta[w]];

		if(ft[x][q].size()==0)return;

	}

}

int main(){

	freopen("glitter.in","r",stdin);

	freopen("glitter.out","w",stdout);

	in(n);

	char c;

	int r;

	rep(q,1,n*n*n){

		in(val[q]);

		if(!val[q])rt.push_back(q);

		while(1){

			r=0;

			while(c=getchar(),c<48);

			do r=(r<<1)+(r<<3)+(c^48);

			while(c=getchar(),c>47);

			son[q].push_back(r);

			if(c=='\n'||c=='\r')break;

		}

	}

	rep(q,0,(int)rt.size()-1){

		int l=0,r=0;

		int now=rt[q];

		mk[now]=-1;

		rep(w,0,(int)son[now].size()-1)mk[son[now][w]]=w+1,mark[son[now][w]]=1,que[++r]=son[now][w];

		while(l<r){

			int nw=que[++l];

			rep(w,0,(int)son[nw].size()-1){

				int to=son[nw][w];

				if(mk[to]==0)mk[to]=mk[nw],mark[to]=mark[nw]+1,que[++r]=to;

				else if(mark[to]==mark[nw]+1)is_used[to]=1;

			}

		}

		rep(w,1,r){

			if(!is_used[que[w]])ft[q][mk[que[w]]-1].push_back(que[w]);

			is_used[que[w]]=0;

			mk[que[w]]=0,mark[que[w]]=0;

		}

		mk[now]=0,mark[now]=0;

	}

	dfs(0);

	printf("%d %d\n",Min,Max);

	return 0;

}

巴特西

「ZJOI2014」璀灿光华

「ZJOI2014」璀灿光华

最新文章

热门文章