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

很久以前就会做了……但是因为听说卡了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);
	}
}

• inline
• block