【BZOJ 4070】[APIO2015] 雅加达的摩天楼

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4070
数据生成器:http://paste.ubuntu.com/23101297/

这个题目,第一眼看就是最短路
然而O(n^2)条边真的是过不了
于是我们分类讨论,将p小于sqrt(n)的边全部建出来,p大于的暴力建
貌似叫分层图?还是看这里吧:http://blog.csdn.net/aarongzk/article/details/51195437?hmsr=toutiao.io
然而随便出一个数据就可以把这个做法搞死QAQ
管他的,卡过就好

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#include<queue>
#include<ctime>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define NUM(p,f) (((p)-1)*(gap+1)+(f))
using namespace std;

const int N = 30005*110;
const int M = 30005*550;
const int INF = 0x3f;
const int inf = 0x3f3f3f3f;

struct Edge{int to,nxt,cost;}e[M];
int head[N],dis[N],inq[N],S,T,n,m,gap;
queue<int> que;

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

inline void AddEdge(int u, int v, int c){
	static int TT = 0; e[++TT].cost = c; 
	e[TT].to = v; e[TT].nxt = head[u]; head[u] = TT;
}

inline int SPFA(int u, int v){
	memset(dis,INF,sizeof(dis));
	dis[u] = 0; que.push(u); inq[u] = 1;
	while (!que.empty()) {
		int w = que.front(); que.pop(); inq[w] = 0;
		for (int i=head[w];i;i=e[i].nxt) if (dis[w]+e[i].cost < dis[e[i].to]) {
			int to = e[i].to;
			dis[to] = dis[w] + e[i].cost;
			if (!inq[to]) que.push(to), inq[to] = 1;
		}
	} 
	if (dis[v] == inf) return -1;
	else return dis[v];
}

int main(){
	n = read(); m = read(); gap = max(1,min(100,(int)sqrt(n))); 
	for (int i=1;i<=n;i++) for (int j=1;j<=gap;j++) AddEdge(NUM(i,j),NUM(i,0),0);
	for (int i=1;i<n;i++) for (int j=1;j<=gap;j++) if (i+j <= n) AddEdge(NUM(i,j),NUM(i+j,j),1); else break;
	for (int i=2;i<=n;i++) for (int j=1;j<=gap;j++) if (i-j > 0) AddEdge(NUM(i,j),NUM(i-j,j),1); else break; 
	for (int i=1,pos,rag;i<=m;i++) {
		pos = read()+1; rag = read();
		if (i == 1) S = NUM(pos,0); if (i == 2) T = NUM(pos,0);
		if (rag > gap) {
			for (int j=pos+rag,t=1;j<=n;j+=rag,t++) AddEdge(NUM(pos,0),NUM(j,0),t);
			for (int j=pos-rag,t=1;j>0;j-=rag,t++) AddEdge(NUM(pos,0),NUM(j,0),t);
		} else AddEdge(NUM(pos,0),NUM(pos,rag),0);
	} printf("%d\n",SPFA(S,T)); 
	return 0;
}

One thought to “【BZOJ 4070】[APIO2015] 雅加达的摩天楼”

Leave a Reply

Your email address will not be published. Required fields are marked *