自动搬运

查看原文

来自洛谷，原作者为

	Durancer Redemption

搬运于2025-08-24 22:26:36，当前版本为作者最后更新于2021-06-11 16:48:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

预处理巨多的状压好题

思路

我不会爆搜啊，太麻烦了。

直接将 $\text{DP}$ 怎么做。

首先需要很多的预处理：

1、处理在每一个深度 $j$ 建立某一个铁路线 $i$ 花费的价格 $\text{cost}_{i,j}$。

2、处理出铁路线 $i$ 和铁路线 $j$ 能否在同一个深度建立线路 $vis_{i,j}$。

3、处理出在深度为 $i$ 的时候，在这一层深度修建的铁路线的状态为 $S$ 价钱 $g_{i,S}$。

处理完这些就可以进行非常短的 $\text{DP}$ 过程了。

限制我们计算价钱的量为深度 $\text{dep}$ ，以及状态 $S$, 那么就考虑设置两维 $\text{DP}$。

设置 $f_{i,S}$ 已经弄完了前 $i$ 深度的铁路线，现在建立完的铁路线编号的状态为 $S$ 的最短价格。

既然我们预处理完了，那么很显然的状态转移就是：

$$f_{i,S}=\min_{s\in S} \{ f_{i-1,S\oplus s}+g_{i,s}\} $$

我们可以用枚举子集的方法避免暴力枚举状态判断。

奇怪的复杂度大约为 ：$O(n^2+2^{14}n^2+2^{14}+2^{14}n)$。(枚举子集的时间复杂度不会算/kk)

可以非常完美的通过此题。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const int N=15;
const int M=1e5+9;
const int K=(1<<15);
const long long int INF=1e18+9;//要开大一点/cg 
int dep[N][M];//深度为 i 的地铁经过了地铁站 j ，的花费
int cnt[N];//表示第 i 条地铁经过的站点个数 
int sub[N][M];//第 i 条地铁经过的站点编号。
int n,m;
long long int f[N][K];//明显跟深度有关，所以就设前i深度，修建的铁路线状态为j的最小花费
long long int g[N][K];//在深度为i时，该层修建状态为j的花费 
long long int cost[N][N];//第i条铁路在深度为j修建时的花费 
bool vis[N][N];//询问第i条铁路和第j条铁路能否修建在一个道路上 
int stk[N],top;
int read()
{
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s^'0');s=getchar();}
	return f*x;
} 
void Prepare()
{
	for(int i=1;i<=n;i++)
		sort(sub[i]+1,sub[i]+1+cnt[i]);//排序，便于查找 
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			vis[i][j]=vis[j][i]=true;
			int x=1,y=1;//一种省时间的方法，序号排好之后，我们可以不断比较编号大小，慢慢递增寻找相同点
			while(x<=cnt[i] and y<=cnt[j])
			{
				if(sub[i][x]==sub[j][y])
				{
					vis[i][j]=vis[j][i]=false;	
					break;//不能在同一条线路上 
				}	
				if(sub[i][x]<sub[j][y]) x++;
				else if(sub[i][x]>sub[j][y]) y++;
			}
		}
	}
	for(int s=1;s<(1<<n);s++)//枚举所有状态 
	{
		top=0;
		for(int i=1;i<=n;i++)
			if(s&(1<<(i-1)))//有戏
			{
				stk[++top]=i;
				for(int j=1;j<top;j++)
					if(!vis[i][stk[j]])//看来没戏了/kk
					{
						for(int k=1;k<=n;k++)//把所有都变为极大值
							g[k][s]=INF;
					}
				if(f[1][s]==INF)//没救了，赋为极大值
					break;
				for(int j=1;j<=n;j++)
					g[j][s]+=cost[i][j];
				//深度为j时修建状态为s的铁路，加上第i条铁路在j深度修建时的总价钱。 
			}
	}
	for(int s=1;s<(1<<n);s++)
		f[1][s]=g[1][s];//初始化第一行 
	return;
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) 
			dep[i][j]=read();
	for(int i=1;i<=n;i++)
	{
		cnt[i]=read();//输入个数
		for(int j=1;j<=cnt[i];j++)
			sub[i][j]=read();
		for(int j=1;j<=n;j++)
			for(int k=1;k<=cnt[i];k++)
				cost[i][j]+=dep[j][sub[i][k]];
	}
	Prepare();
	for(int i=2;i<=n;i++)
	{
		for(int S=0;S<(1<<n);S++)
		{
			f[i][S]=f[i-1][S];//初始化,加入这个不选 
			for(int s=S;s;s=(s-1)&S)
				f[i][S]=min(f[i][S],f[i-1][S^s]+g[i][s]);
		}	
	} 
	cout<<f[n][(1<<n)-1]<<endl;
	return 0;
}