【CodeChef】Find a special connected block - CONNECT（斯坦纳树）

题面

题解

还是一样的套路题，把每个数字映射到\([0,K)\)的整数，然后跑斯坦纳树，重复多次就有很大概率出解。

但是别乱随机，我直接随机\(WA\)成sb了，后来学了别人代码用自己手写的伪随机数就过了。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#include<map>

using namespace std;

#define ll long long

#define MAX 16

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

map<int,int> M;

int n,m,K,ans=2e9;

int a[MAX*MAX],b[MAX*MAX],c[MAX*MAX];

int f[1<<7][MAX*MAX];

queue<int> Q;bool vis[MAX*MAX];

vector<int> E[MAX*MAX];

int ID(int x,int y){return (x-1)*m+y;}

int d[4][2]={-1,0,0,-1,1,0,0,1};

void SPFA(int S)

{

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int v:E[u])

			if(f[S][v]>f[S][u]+b[v])

			{

				f[S][v]=f[S][u]+b[v];

				if(!vis[v]&&f[S][v]<=ans)vis[v]=true,Q.push(v);

			}

		vis[u]=false;

	}

}

unsigned int Rand()

{

	static unsigned int x=19260817;

	x^=(x<<5);x^=(x>>17);x^=(x<<13);

	return x;

}

int main()

{

	n=read();m=read();K=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)a[ID(i,j)]=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)b[ID(i,j)]=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			if(~a[ID(i,j)])

				for(int k=0;k<4;++k)

				{

					int x=i+d[k][0],y=j+d[k][1];

					if(x<1||y<1||x>n||y>m||a[ID(i,j)]==-1)continue;

					E[ID(i,j)].push_back(ID(x,y));

				}

	for(int Tim=1;Tim<=500;++Tim)

	{

		M.clear();

		for(int i=1;i<=n*m;++i)

			if(~a[i])

			{

				if(!M.count(a[i]))M[a[i]]=Rand()%K;

				c[i]=M[a[i]];

			}

		memset(f,63,sizeof(f));

		for(int i=1;i<=n*m;++i)if(~a[i])f[a[i]?(1<<c[i]):0][i]=b[i];

		for(int S=0;S<(1<<K);++S)

		{

			for(int i=1;i<=n*m;++i)

			{

				if(a[i]==-1)continue;

				for(int T=(S-1)&S;T;T=(T-1)&S)

					f[S][i]=min(f[S][i],f[T][i]+f[S^T][i]-b[i]);

				if(f[S][i]<=ans)Q.push(i),vis[i]=true;

			}

			SPFA(S);

		}

		for(int i=1;i<=n*m;++i)if(~a[i])ans=min(ans,f[(1<<K)-1][i]);

	}

	printf("%d\n",(ans>1e9)?-1:ans);

	return 0;

}

巴特西

【CodeChef】Find a special connected block - CONNECT（斯坦纳树）

【CodeChef】Find a special connected block - CONNECT（斯坦纳树）

题面

题解

最新文章

热门文章