2007: [Noi2010]海拔 - #include <Seter> - using namespace Orz;

2007: [Noi2010]海拔

Seter posted @ 2011年12月12日 21:17 in BZOJ with tags NOI NetworkFlow SegTree , 2768 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2007

RunID User Problem Result Memory Time Language Code Length Submit Time
177134 Seter 2007 Accepted 25752 kb 200 ms C/Edit 1288 B 2011-12-12 20:41:23

很久以前就会做了……但是因为听说卡了SPFA所以一直拖着(C党没有heap的STL真是个悲剧!)然后前几天终于准备A这题了……先写了个SPFA,各种SB,交到TYVJ上结果TLE一个点,然而奇葩的是,加了fread的的读入优化后居然TLE两个点……

XTY给我讲这题的时候很WS地改了题目……他把起点和终点的高度改成给定两个实数……(其实是一样的)然后我说,这个不是唬人的嘛……

注意到每个点高度不是0就是1,然后最小割肯定没错……(在残量网络中,与起点相连的标0,与终点相连的标1即可)

最小割肯定过不了,怎么办呢……和狼抓兔子这题一样,平面图中,最小割=最短路(而且这题反而是这种思路比较容易想到)。从右上角拉一条线到左下角,那么线的左上方就是0,右下方就是1,线的长度=割掉的边长度。即,把每个格子抽象成一个点,每个点像上下左右四个点连边。

那么边权是多少呢?举个例子。比如原图中格子i,j上边那条边从左到右边权是x,如果割掉这条边,那么相当于取了哪条绳子呢?这条绳子必定横跨这条边(即i-1,j与i,j的连边),割掉这条边说明此格子左上角是0,右上角是1,画图后很容易发现这条边必定由上至下。于是乎构图就可以了。

几个测试:

SPFA+SLF+距离大于等于终点距离时剪枝TYVJ上很慢,但是能A。BZOJ较快AC。

DIJKSTRA,Rank2秒杀……Rank1才187MS,真心不想写堆了……

ZKW线段树真是个好东西……以前因为懒得写堆所以懒得写DIJKSTRA,用ZKW线段树以后DIJKSTRA比SPFA还短好多,而且不比堆慢……以后对正权图就不用SPFA了……

 

#include <stdio.h>
#include <string.h>
#define inf 0x7F7F7F7F
#define get(i,j) i==-1||j==n?s:j==-1||i==n?t:(i)*n+j
#define ADDEDGE(u,v) p->y=v,p->next=map[u],(map[u]=p++)->t=getint()
#define init(i) a[i]=dis[a[i<<1]]<dis[a[i<<1^1]]?a[i<<1]:a[i<<1^1]
struct edge{struct edge *next;int t,y;}*map[250002],st[1100000],*p=st;
int n,M,dis[262144],a[524288],s,t;_Bool v[250002];
char str[8000000],*q=str;
inline getint(){
	int re=0;
	while(*q<'0'||*q>'9')q++;
	while(*q>='0'&&*q<='9')re=re*10+*q++-48;
	return re;
}inline void updt(i,x){for(dis[i]=x,i^=M;i>>=1;init(i))if(dis[a[i]]<x)return;}
main(){
	int i=-1,j;fread(q,1,8000000,stdin);n=getint();
	memset(dis,0x7F,(M=1<<32-__builtin_clz(t=1+(s=n*n)))<<2);dis[s]=0;
	while(i++!=M)a[M^i]=i;for(i=M;--i;init(i));
	for(i=-1;i++!=n;)for(j=-1;++j!=n;)ADDEDGE(get(i-1,j),get(i,j));
	for(i=-1;++i!=n;)for(j=-1;j++!=n;)ADDEDGE(get(i,j),get(i,j-1));
	for(i=-1;i++!=n;)for(j=-1;++j!=n;)ADDEDGE(get(i,j),get(i-1,j));
	for(i=-1;++i!=n;)for(j=-1;j++!=n;)ADDEDGE(get(i,j-1),get(i,j));
	for(;dis[i=a[1]]!=inf;updt(i,inf)){
		if(i==t)return printf("%d\n",dis[t]),0;
		for(v[i]=1,p=map[i];p;p=p->next)if(!v[p->y]&&dis[p->y]>dis[i]+p->t)updt(p->y,dis[i]+p->t);
	}
}
By Seter

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee