NOIP2013 货车运输【最大生成树+LCA】+华容道【BFS建图+SPFA】

tonyfang posted @ 2015年9月08日 16:39 in NOIP with tags c++ OI , 511 阅读

货车运输:容易看出,只会在最大生成树边上跑,那么就求最大生成树,然后求两个点LCA路径中的最小值即可。

华容道:坑!!!BFS来预处理建图,$step[i,j,k,l]$表示在$(i,j)$,空格在$k$方向,向$l$方向移动一格的步数。

然后就可以把$id[i,j,k]$和$id[i',j',k']$连边建图啦。建完图跑SPFA,特判一堆情况。

 

# include <stdio.h>
# include <algorithm>
# include <iostream>
using namespace std;
int n,m,fa[10010];
struct E {
	int u,v,w;
}e[100010];
int head[10010],next[100010],to[100010],w[100010],tot;
inline int find(int x) {
	int r=x;
	while(fa[r]!=r) 
		r=fa[r];
	int i=x,j;
	while(i!=r) {
		j=fa[i];
		fa[i]=r;
		i=j;
	}
	return r;
}
inline bool cmp(E a,E b) {
	return a.w > b.w;
}
inline void add(int x,int y,int z) {
	tot++;
	next[tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
int f[10010][15],g[10010][15];
// f: 理论树上边权1,g: 实际边权 
int level[10010];
void dfs(int x,int lev) {
	level[x]=lev;
	for (int i=1;i<=14;++i) {
		f[x][i]=f[f[x][i-1]][i-1];
		g[x][i]=min(g[x][i-1],g[f[x][i-1]][i-1]);
	}
	for (int i=head[x];i;i=next[i]) {
		if(!level[to[i]]) {
			f[to[i]][0]=x;
			g[to[i]][0]=w[i];
			dfs(to[i],lev+1);
		}
	}
}
inline int lca(int u,int v) {
	if (level[u]>level[v]) {int t=u;u=v;v=t;}	
	int ans=210000000;
	for (int i=14;i>=0;--i) {
		if(level[f[v][i]]>=level[u]) {
			ans=min(ans,g[v][i]);
			v=f[v][i];
		}
	}
	if(u==v) return ans;
	for (int i=14;i>=0;--i) {
		if(f[u][i]!=f[v][i]) {
			ans=min(ans,min(g[u][i],g[v][i]));
			u=f[u][i],v=f[v][i];
		}
	}
	ans=min(ans,min(g[u][0],g[v][0]));
	return ans;
}
main() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	for (int i=1;i<=n;++i) fa[i]=i;
	sort(e+1,e+m+1,cmp);
	//for (int i=1;i<=m;++i) 
	//	printf("%d %d %d\n",e[i].u,e[i].v,e[i].w);
	for (int i=1;i<=m;++i) {
		int fu=find(e[i].u),fv=find(e[i].v);
		if(fu!=fv) {
			add(e[i].u,e[i].v,e[i].w);
			add(e[i].v,e[i].u,e[i].w);
			fa[fu]=fv;
		}
	}
	//======end kruskal========
	//======lca========
	for (int i=1;i<=n;++i)
		if(!level[i]) dfs(i,1);
	int TestCases;
	scanf("%d",&TestCases);
	while(TestCases--) {
		int u,v;
		scanf("%d%d",&u,&v);
		if(find(u)!=find(v)) printf("-1\n");
		else printf("%d\n",lca(u,v));
	}
}

 

# include <stdio.h>
# include <queue>
# include <vector> 
# include <string.h>
# define OO __attribute__((optimize("-O2")))
using namespace std;
int n,m,Q;
const int Max=110,INF=0x3f3f3f3f;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int map[Max][Max],id[Max][Max][4],cnt;
int head[10010],next[100010],to[100010],w[100010],tot;
int step[Max][Max][4][4];
queue< pair<int,int> > q;
# define MP make_pair
OO inline void add(int x,int y,int z) {
	tot++;
	next[tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
int dis[Max][Max];
OO inline int bfs(int sx,int sy,int tx,int ty) {
	while(!q.empty()) q.pop();
	if(sx==tx&&sy==ty) return 0;
	memset(dis,INF,sizeof(dis));
	dis[sx][sy]=0;q.push(MP(sx,sy));
	while(!q.empty()) {
		pair<int,int> p = q.front();
		int xx=p.first,yy=p.second;
		q.pop();
		for (int i=0;i<4;++i) {
			int xxx=xx+dx[i],yyy=yy+dy[i];
			if(xxx>=1&&xxx<=n&&yyy>=1&&yyy<=m&&map[xxx][yyy]&&dis[xxx][yyy]==INF) {
				dis[xxx][yyy]=dis[xx][yy]+1;
				if(xxx==tx&&yyy==ty)
					return dis[xxx][yyy];
				q.push(MP(xxx,yyy));
			}
		} 
	}
	return INF;
}
queue<int> qq;
int d[50010],vis[50010];
OO inline int spfa (int S,int T) {
	while(!qq.empty()) qq.pop();
	memset(vis,0,sizeof(vis));
	memset(d,INF,sizeof(d));
	d[S]=0;vis[S]=1;qq.push(S);
	while(!qq.empty()) {
		int top=qq.front();qq.pop();
		vis[top]=0;
		for (int i=head[top];i;i=next[i]) {
			int _to=to[i];
			if(d[_to]>d[top]+w[i]) {
				d[_to]=d[top]+w[i];
				if(!vis[_to]) {
					qq.push(_to);
					vis[_to]=1;
				}
			}
		}
	}
	if(d[T]<INF) return d[T];
	else return -1;
}
OO inline void work(int kx,int ky,int sx,int sy,int tx,int ty) {
	int S=++cnt,T=++cnt;
	map[sx][sy]=0;
	for (int i=0;i<4;++i) {
		int x=sx+dx[i],y=sy+dy[i];
		if (map[x][y]) {
			int t=bfs(kx,ky,x,y);
			if(t<INF) add(S,id[sx][sy][i],t);
		}
	}
	map[sx][sy]=1;
	for (int i=0;i<4;++i) {
		int x=tx+dx[i],y=ty+dy[i];
		if (map[x][y]) add(id[tx][ty][i],T,0);
	}
	printf("%d\n",spfa(S,T));
}
OO int main() {
	scanf("%d%d%d",&n,&m,&Q);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) 
			scanf("%d",&map[i][j]);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			for (int k=0;k<4;++k)
				id[i][j][k]=++cnt; 
	memset(step,INF,sizeof(step));
	for (int i=1;i<=n;++i) 
		for (int j=1;j<=m;++j)
			if(map[i][j]) {
				map[i][j]=0;
				for (int k=0;k<4;++k) {
					int xx=i+dx[k],yy=j+dy[k];
					if(map[xx][yy]) {
						for (int l=0;l<4;++l) {
							int xxx=i+dx[l],yyy=j+dy[l];
							if(map[xxx][yyy]) step[i][j][k][l]=bfs(xx,yy,xxx,yyy)+1;
						} 
					}
				}
				map[i][j]=1;
			}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			for (int k=0;k<4;++k)
				for (int l=0;l<4;++l) 
					if (step[i][j][k][l]<INF) add(id[i][j][k],id[i+dx[l]][j+dy[l]][l^1],step[i][j][k][l]);
	
	while(Q--) {
		int kx,ky,sx,sy,tx,ty;
		scanf("%d%d%d%d%d%d",&kx,&ky,&sx,&sy,&tx,&ty);
		if (sx==tx&&sy==ty) {
			printf("0\n");
			continue;
		}
		if (!map[sx][sy] || !map[tx][ty]) {
			printf("-1\n");
			continue;
		}
		if(sx<1||sx>n||sy<1||sy>m||tx<1||tx>n||ty<1||ty>m||kx<1||kx>n||ky<1||ky>m) {
			printf("-1\n");
			continue;
		}
		work(kx,ky,sx,sy,tx,ty);
	} 
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter