luoguP4294 [WC2008]游览计划

题意

斯坦纳树裸题。

显然答案是棵树。

设\(f[i][s]\)表示以\(i\)为根，集合为\(s\)的最小代价。

先在同根之间转移：

\(f[i][s]=min(f[i][t]+f[i][s\ xor\ t]-val[i])\)

减\(val[i]\)是因为算了两遍。

之后扩展新点：

\(f[i][s]=min(f[j][s]+val[i]),(i,j)\)联通，这个可以用\(spfa\)。

code:

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int,int>

#define mkp make_pair

#define fir first

#define sec second

const int maxn=12;

const int dx[]={-1,1,0,0};

const int dy[]={0,0,-1,1};

int n,m,K,tot,root,ans=0x3f3f3f3f;

int id[maxn][maxn],a[maxn][maxn],f[maxn*maxn][1<<maxn];

pii pos[maxn*maxn],g[maxn*maxn][1<<maxn];

bool vis[maxn*maxn];

bool check[maxn][maxn];

vector<int>keypoints;

queue<int>q;

inline void spfa(int s)

{

	while(!q.empty())

	{

		int x=q.front();q.pop();vis[x]=0;

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

		{

			int mx=pos[x].fir+dx[i],my=pos[x].sec+dy[i];

			if(mx<1||mx>n||my<1||my>m)continue;

			int y=id[mx][my];

			if(f[y][s]>f[x][s]+a[pos[y].fir][pos[y].sec])

			{

				f[y][s]=f[x][s]+a[pos[y].fir][pos[y].sec];

				if(!vis[y])vis[y]=1,q.push(y);

				g[y][s]=mkp(x,s);

			}

		}

	}

}

void dfs(int now,int s)

{

	if(!g[now][s].sec)return;

	check[pos[now].fir][pos[now].sec]=1;

	if(g[now][s].fir==now)dfs(now,s^g[now][s].sec);

	dfs(g[now][s].fir,g[now][s].sec);

}

int main()

{

	scanf("%d%d",&n,&m);

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

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

			scanf("%d",&a[i][j]),id[i][j]=++tot,pos[tot]=mkp(i,j);

	memset(f,0x3f,sizeof(f));

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

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

			if(!a[i][j])f[id[i][j]][1<<K]=0,K++,keypoints.push_back(id[i][j]);

	for(int s=1;s<(1<<K);s++)

	{

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

		{

			for(int t=s&(s-1);t;t=(t-1)&s)

				if(f[i][s]>f[i][s^t]+f[i][t]-a[pos[i].fir][pos[i].sec])

				{

					f[i][s]=f[i][s^t]+f[i][t]-a[pos[i].fir][pos[i].sec];

					g[i][s]=mkp(i,t);

				}

			if(f[i][s]<0x3f3f3f3f)q.push(i),vis[i]=1;

		}

		spfa(s);

	}

	for(unsigned int i=0;i<keypoints.size();i++)

		if(ans>f[keypoints[i]][(1<<K)-1])ans=f[keypoints[i]][(1<<K)-1],root=keypoints[i];

	printf("%d\n",ans);

	dfs(root,(1<<K)-1);

	for(int i=1;i<=n;i++,puts(""))

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

			if(!a[i][j])putchar('x');

			else putchar(check[i][j]?'o':'_');

	return 0;

}

巴特西

luoguP4294 [WC2008]游览计划

题意

最新文章

热门文章