题解：P4796 [BalticOI 2018] 路径

P4796 [BalticOI 2018] 路径

方法：记忆化搜索。
首先根据题意，可以先打个暴搜，可以得到 $70$ 分。

暴力搜索

CPP

12345678910  il void dfs(int u,int fa){
	if(vis[a[u]]) return ;
	vis[a[u]]=1;
	if(fa) ++ans;
	for(int v:g[u]){
		if(v==fa) continue;
		dfs(v,u);
	}
	vis[a[u]]=0;
}

然后考虑优化，注意到一个点可能会遍历多次，并且状态可能一致（即相同颜色集合），考虑用记忆化数组存储，第一维表示点，第二维表示颜色集合，由于 $k \le 5$ ，可以用状压来表示，转移可以用以下式子表示： $f_{i,S}=1 + \sum_{(i,j) \in E,a_j \notin S} f_{j,S \cup a_j}$
最后答案就是 $\sum_{i=1}^n f_{i,a_i}-n$ ，因为路径长 $>1$ ，所以减去 $n$ 。总复杂度为 $O((n+m) \times 2^k)$ 。

code

CPP

123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
il ll read(){
	ll x=0;bool f=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int N=3e5+5;
int a[N];
vector<int> g[N];
ll mem[N][1<<5];
int n,m,k;
il void solve();
int main()
{
//	freopen("path.in","r",stdin);
//	freopen("path.out","w",stdout);
	solve();
	return 0;
}
il ll dfs(int u,int fa,int val){
	if((val&(1<<(a[u]-1)))||a[u]>k) return 0;
	int p=val|(1<<(a[u]-1));
	if(mem[u][p]!=-1) return mem[u][p];
	ll res=1;
	for(int v:g[u]){
		if(v==fa) continue;
		res+=dfs(v,u,p);
	}
	return mem[u][p]=res;
}
il void solve(){
	n=read(),m=read(),k=read();
	memset(mem,-1,sizeof(mem));
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1,u,v;i<=m;++i)
		u=read(),v=read(),
		g[u].push_back(v),g[v].push_back(u);
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=dfs(i,0,0);
	printf("%lld\n",ans-n);
}

完结撒花。

题解：P4796 [BalticOI 2018] 路径

文章操作

P4796 [BalticOI 2018] 路径

相关推荐

评论

题解：P4796 [BalticOI 2018] 路径