http://acm.hdu.edu.cn/showproblem.php?pid=5385
题意：
给定一张n个点m条有向边的图，构造每条边的边权（边权为正整数），令d(x)表示1到x的最短路，使得存在点i(1<=i<=n)满足d(1)<d(2)<…<d(i)>d(i+1)>…>d(n)。
从两边向中间构造。
开始L=1，R=n
从L开始bfs，顺次构造L，L+1，L+2……
构造不动了再从R开始bfs，顺次构造R，R-1，R-2……
然后在从L开始……
直到L>=R
第j个bfs到的点，就令它的dis[i]=j
边u-->v的边权即为 dis[v]-dis[u] 的绝对值
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 int n,m; struct node
{
int u,v;
}e[N]; int front[N],nxt[N],to[N],tot; bool vis[N];
int dis[N]; int L,R;
int id; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
} void bfs(int &s,int k)
{
while(s> && s<=n)
{
if(!vis[s]) return;
if(dis[s]!=-) return;
dis[s]=id++;
for(int i=front[s];i;i=nxt[i]) vis[to[i]]=true;
s+=k;
}
} int main()
{
int T,x;
read(T);
while(T--)
{
tot=;
memset(front,,sizeof(front));
read(n); read(m);
for(int i=;i<=m;++i)
{
read(e[i].u);
read(e[i].v);
add(e[i].u,e[i].v);
}
memset(vis,false,sizeof(vis));
memset(dis,-,sizeof(dis));
vis[]=true;
L=; R=n;
id=;
while(L<R)
{
bfs(L,);
bfs(R,-);
}
for(int i=;i<=m;++i)
{
x=abs(dis[e[i].u]-dis[e[i].v]);
if(!x) x=n;
printf("%d\n",x);
}
}
}