专栏文章

P13489 [GCJ 2008 Finals] Bridge Builders

RRigel
P13489题解参与者 8已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@minvo3fl
此快照首次捕获于
2025/12/02 09:06
3 个月前
此快照最后确认于
2025/12/02 09:06
3 个月前
查看原文

思路

首先计算出任意两个可达格子（除海洋以外的格子）之间的距离。在所有可达格子和与其四方向相邻的可达格子之间连边，边权为 11。从每个格子开始跑 Dijkstra，求出任意两个格子之间的最短路，即它们之间的距离。
先不考虑森林之间的连通情况，假设每个普通岛屿只需与任一森林连通。不难得出，对于每个普通岛屿，将其连通的最小费用为它与离它最近的森林的距离。
然后考虑将所有森林连通。
对于森林 u,vu,v，需要计算出将它们相连的额外费用 ww。
设 u,vu,v 的距离为 dd。
当 dmod  2=0d \mod 2 = 0 时，如图所示，蓝色为将普通岛屿连接至森林的费用，红色为原图中的格子均未连通时连通 u,vu,v 的费用。
此时额外费用 w=(d2+1+d)×d22−(1+d2−1)×(d2−1)2=d24+d2w = \dfrac{(\dfrac{d}{2} + 1 + d) \times \dfrac{d}{2}}{2} - \dfrac{(1 +\dfrac{d}{2} - 1) \times (\dfrac{d}{2} - 1)}{2} = \dfrac{d^2}{4} + \dfrac{d}{2}。
当 dmod  2=1d \mod 2 = 1 时，如图所示。
此时额外费用 w=(⌊d2⌋+1+d)×(⌊d2⌋+1)2−(1+⌊d2⌋)×⌊d2⌋2=(d+1)(⌊d2⌋+1)2w = \dfrac{(\lfloor \dfrac{d}{2} \rfloor + 1 + d) \times (\lfloor \dfrac{d}{2} \rfloor + 1)}{2} - \dfrac{(1 +\lfloor \dfrac{d}{2} \rfloor) \times \lfloor \dfrac{d}{2} \rfloor}{2} = \dfrac{(d+1)(\lfloor \dfrac{d}{2} \rfloor + 1)}{2}。
综上，额外费用 w={d24+d2dmod  2=0,(d+1)(⌊d2⌋+1)2dmod  2=1.w = \begin{cases} \dfrac{d^2}{4} + \dfrac{d}{2} & d \mod 2 = 0,\\ \\ \dfrac{(d+1)(\lfloor \dfrac{d}{2} \rfloor + 1)}{2} & d \mod 2 = 1. \end{cases}
计算将任意两个森林相连的额外费用，将其作为连接这两个森林的边的边权。对所有森林跑 Kruskal 求 MST 即可。
最终答案即为将所有普通岛屿连接至森林的费用加上连通所有森林的额外费用。
可以证明此方案最优。
时间复杂度瓶颈在于 Dijkstra 的 O((NM)2log⁡(NM))\mathcal{O}((NM)^2\log(NM))，故总复杂度为 O(T(NM)2log⁡(NM))\mathcal{O}(T(NM)^2\log(NM))。

Code

CPP
#include<bits/stdc++.h>
#define int long long

const int N=35; 

using namespace std;

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

int T,n,m,tim,tt,tot0,tot,cnt,fa[N*N],t[N*N],lnk[N*N],vis[N*N],dis[N*N][N*N],ans;

char c[N][N];

struct node{
	int x,dis;
	bool operator<(const node &b)const{return dis>b.dis;}
};

struct edge0{
	int to,w,nxt;
}e0[N*N*N*N*2];

struct edge{
	int u,v,w;
	bool operator<(const edge &b)const{return w<b.w;}
}e[N*N*N*N];

priority_queue<node>q;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
	return ret*f;
}

inline char read1(){
	char ch=getchar();
	while(ch!='T'&&ch!='#'&&ch!='.')ch=getchar();
	return ch;
}

bool chk(int i,int j){
	if(i<1||j<1||i>n||j>m)return 0;
	return c[i][j]!='.';
}

int getid(int i,int j){
	return (i-1)*m+j;
}

void add_e(int x,int y,int z){
	e0[++tot0]=(edge0){y,1,lnk[x]};
	lnk[x]=tot0;
}

void Dij(int st){
	for(int i=1;i<=n*m;i++)vis[i]=0;
	dis[st][st]=0;
	while(!q.empty())q.pop();
	q.push({st,0});
	while(!q.empty()){
		int u=q.top().x;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=lnk[u];i;i=e0[i].nxt){
			int v=e0[i].to;
			if(dis[st][u]+e0[i].w<dis[st][v]){
				dis[st][v]=dis[st][u]+e0[i].w;
				q.push({v,dis[st][v]});
			}
		}
	}
}

void _init(){
	tt=tot0=tot=cnt=0;
	for(int i=1;i<=n*m;i++){
		fa[i]=i;
		lnk[i]=0;
		for(int j=1;j<=n*m;j++)dis[i][j]=1e9;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!chk(i,j))continue;
			if(c[i][j]=='T')t[++tt]=getid(i,j);
			for(int k=0;k^4;k++){
				int x=i+f[k][0],y=j+f[k][1];
				if(!chk(x,y))continue;
				int u=getid(i,j),v=getid(x,y);
				add_e(u,v,1);
			}
		}
	}
	for(int i=1;i<=n*m;i++)Dij(i);
}

int _calc(int u,int v){
	int d=dis[u][v];
	if(d&1)return (d+1)*((d/2)+1)/2;
	return d*d/4+d/2;
}

int getfa(int x){
	return (fa[x]==x)?x:(fa[x]=getfa(fa[x]));
}

void _solve(){
	tim++;
	n=read(),m=read(),ans=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)c[i][j]=read1();
	_init();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(c[i][j]=='#'){
				int id=getid(i,j),w=1e9;
				for(int k=1;k<=tt;k++)w=min(w,dis[id][t[k]]);
				ans+=w;
			}
		}
	}
	for(int i=1;i<=tt;i++)for(int j=i+1;j<=tt;j++)e[++tot]=(edge){t[i],t[j],_calc(t[i],t[j])};
	sort(e+1,e+tot+1);
	for(int i=1;i<=tot;i++){
		int fx=getfa(e[i].u),fy=getfa(e[i].v);
		if(fx^fy){
			fa[fx]=fy;
			ans+=e[i].w;
			cnt++;
			if(cnt==tt-1)break;
		}
	}
	printf("Case #%lld: %lld\n",tim,ans);
}

signed main(){
	T=read();
	while(T--)_solve();
	return 0;
}

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...