2007: [Noi2010]海拔 - #include <Seter> - using namespace Orz;
2007: [Noi2010]海拔
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了……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #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
评论 (0)