[文章目录]
Description
有n(1 <= n <= 10000)头牛从１到n线性排列，每头牛的高度为h[i] (1 <= i <= n),现在告诉你这里面的牛的最大高度为maxH,而且有r组关系，每组关系输入两个数字，假设为a和b,表示第a头牛能看到第b头牛，能看到的条件是a, b之间的其它牛的高度都严格小于min(h[a], h[b]),而h[b] >= h[a]
差分约束，分块优化建图。（话说可以线段树优化啊）
然而我做矬了，发现给你的区间（a,b）互相不会包含。
那么直接将区间差分，考虑每个点被多少个区间包含，计算权值即可。
#include <cmath>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,h,m,b[11000];
int head[11000],to[3100000],nxt[3100000],f[3100000],cnt;
int dis[11000];
bool vis[11000];
queue<int>q;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x];
head[x]=cnt; f[cnt]=z;
}
void spfa()
{
for(int i=1;i<=b[n];++i) q.push(i),vis[i]=1,dis[i]=h;
int x;
while(!q.empty())
{
x=q.front(); q.pop(); vis[x]=0;
for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>dis[x]+f[i])
{
dis[to[i]]=dis[x]+f[i];
if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
}
}
}
int main()
{
scanf("%d%*d%d%d",&n,&h,&m);
int blo=(int)sqrt((double)n)+2;
b[0]=n;
for(int i=1;i<=n;++i)
{
if(i%blo==1) b[i]=b[i-1]+1;
else b[i]=b[i-1];
add(b[i],i,0);
}
int x,y,l,r,L,R;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
add(y,x,0); L=min(x,y)+1; R=max(x,y)-1;
for(l=L;l<=R;++l)
{
if(l%blo!=1) add(x,l,-1);
else break;
}
for(r=R;r>=l;--r)
{
if(r%blo!=0) add(x,r,-1);
else break;
}
if(l<r) for(int j=b[l];j<=b[r];++j) add(x,j,-1);
}
spfa();
for(int i=1;i<=n;++i) printf("%d\n",dis[i]);
return 0;
}