洛谷 P7450 - [THUSCH2017] 巧克力（斯坦纳树+随机化）

9.13 补之前 8.23 做的题，不愧是鸽子 tzc（

首先我们先来探讨一下如果 \(c_{i,j}\le k\) 怎么做，先考虑第一问。显然一个连通块符合条件当且仅当它能够包含所有颜色。我们注意到这里的 \(k\) 数据范围很小，因此考虑状压 \(dp\)。\(dp_{x,y,S}\) 表示包含 \((x,y)\) 且囊括了 \(S\) 中所有颜色的最小连通块的大小。那么有转移 \(dp_{x,y,S}+1\to dp_{x+1,y,S\cup\{c_{x+1,y}\}}\)，其余三个方向上的转移也同理。注意这样直接转移有后效性，不过注意到这种后效性只可能发生在 \(c_{x+1,y}\in S\) 的情况，因此我们考虑这样转移：从小到大枚举 \(S\)，然后对于每个 \(dp_{x,y,S}\) 更新 \(dp_{x,y,S}=\min\limits_{S_1\cup S_2=S}\{dp_{x,y,S_1}+dp_{x,y,S_2}-1\}\)，之后再用 \(dp_{x,y,S}\) 去更新周围的点，即 \(dp_{x,y+1,S}\leftarrow dp_{x,y,S}+1\)，类似于一个最短路的过程。不难发现上述过程中使用了取 \(\min/\max\) 的 DP 的一个思想：我的 DP 转移贡献不一定合法，但我不合法的情况肯定没有合法的情况来得更优。在上面的 DP 转移中有可能出现转移到的 \(S\) 等于我们转移所产生贡献的连通块真正包含的颜色集合，但这个包含关系是必然成立的，因此最优解肯定会被我囊括在内。据说这就是斯坦纳树的基本思想？反正也算一个非常 trivial 的知识点吧（

接下来考虑第二问。其实也非常套路吧……考虑二分中位数 \(mid\)，然后把 \(\le mid\) 都设为 \(-1\)，\(>mid\) 都设为 \(1\)，这样可以仿照之前的解法求出在满足连通块大小最小的情况，最小的权值和，如果最小权值和 \(\le 0\) 则说明这个中位数符合条件，应向左二分，否则应向右二分。正确性显然，总复杂度大概是 \(2^k·\log^2(nm)·nm\)。

接下来考虑原问题。显然对于原题的数据范围而言，直接上个状压 dp 就不可取了。不过这个思想还是很有启发意义的。考虑最优解连通块中的颜色种类 \(S\)，我们希望能够重新分组使得颜色个数 \(\le k\)，并且恰好满足 \(S\) 中的颜色被分在了至少 \(k\) 组中，有什么好方法呢？随机化，考虑随机将 \(nm\) 种颜色分组，那么最优解刚好被分在 \(k\) 个不同的组中的概率大概是 \(\dfrac{k!}{k^k}\)，当 \(k=5\) 时这个概率大概在百分之几，随机个 \(150\) 次出错的概率就很低了。

时间复杂度 \(T·150·2^k·\log^2(nm)·nm\)，非常卡常。然后我反向套路一波，把 dij 换成 SPFA（真·网格图 SPFA）就过了（？）

const int MAXN=233;

const int MAXP=32;

const int INF=1061109567;

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

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

int n,m,k,a[MAXN+5][MAXN+5],c[MAXN+5][MAXN+5];

int va[MAXN+5],col[MAXN+5],id[MAXN+5][MAXN+5],cc[MAXN+5],cnt=0;

int hd[MAXN+5],to[MAXN*4+5],nxt[MAXN*4+5],ec=0;

void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}

bool vis[MAXN+5];

pii dp[MAXN+5][MAXP+5],b[MAXN+5];

pii operator +(pii x,pii y){return mp(x.fi+y.fi,x.se+y.se);}

pii operator -(pii x,pii y){return mp(x.fi-y.fi,x.se-y.se);}

void dijkstra(int s){

	queue<int> q;

	for(int i=1;i<=cnt;i++) q.push(i),vis[i]=1;

	while(!q.empty()){

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

		for(int e=hd[x];e;e=nxt[e]){

			int y=to[e];

			if(dp[y][s]>dp[x][s]+b[y]){

				dp[y][s]=dp[x][s]+b[y];

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

			}

		}

	}

}

pii check(int mid){

	for(int i=1;i<=cnt;i++) for(int s=0;s<(1<<k);s++) dp[i][s]=mp(INF,INF);

	for(int i=1;i<=cnt;i++){

		if(va[i]<=mid) dp[i][1<<(col[i]-1)]=dp[i][0]=b[i]=mp(1,-1);

		else dp[i][1<<(col[i]-1)]=dp[i][0]=b[i]=mp(1,1);

	}

	for(int s=0;s<(1<<k);s++){

		for(int i=1;i<=cnt;i++){

			for(int t=(s-1)&s;t;t=(t-1)&s) chkmin(dp[i][s],dp[i][t]+dp[i][s^t]-b[i]);

		} dijkstra(s);

	} pii res=mp(INF,INF);

	for(int i=1;i<=cnt;i++) chkmin(res,dp[i][(1<<k)-1]);

	return res;

}

pii work(){

	int l=0,r=1e6,res=check(0).fi,p=INF;

	if(res==INF) return mp(INF,INF);

	while(l<=r){

		int mid=l+r>>1;

		if(check(mid).se<=0) p=mid,r=mid-1;

		else l=mid+1;

	}

	return mp(res,p);

}

void clear(){

	memset(hd,0,sizeof(hd));ec=0;

	memset(id,0,sizeof(id));cnt=0;

}

void solve(){

	scanf("%d%d%d",&n,&m,&k);pii res=mp(INF,INF);clear();

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&c[i][j]);

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(~c[i][j]) id[i][j]=++cnt,va[cnt]=a[i][j];

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int d=0;d<4;d++){

		int x=i+dx[d],y=j+dy[d];

		if(x<1||x>n||y<1||y>m||!id[x][y]) continue;

		adde(id[i][j],id[x][y]);

	}

	int ______=150;

	while(______--){

		for(int i=1;i<=n*m;i++) cc[i]=rand()%k+1;

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

			if(id[i][j]) col[id[i][j]]=cc[c[i][j]];

		chkmin(res,work());

	} if(res.fi==INF) printf("-1 -1\n");

	else printf("%d %d\n",res.fi,res.se);

}

int main(){

	srand(20210823183524ll&4294967295);

	int qu;scanf("%d",&qu);while(qu--) solve();

	return 0;

}

巴特西

洛谷 P7450 - [THUSCH2017] 巧克力（斯坦纳树+随机化）

最新文章

热门文章