The path
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 995 Accepted Submission(s): 419
Special Judge
Problem Description
You have a connected directed graph.Let d(x) be the length of the shortest path from 1 to x.Specially d(1)=0.A graph is good if there exist x satisfy d(1)<d(2)<....d(x)>d(x+1)>...d(n).Now you need to set the length of every edge satisfy that the graph is good.Specially,if d(1)<d(2)<..d(n),the graph is good too.
The length of one edge must ∈ [1,n]
It's guaranteed that there exists solution.
The length of one edge must ∈ [1,n]
It's guaranteed that there exists solution.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m,the number of vertexs and the number of edges.Next m lines contain two integers each, ui and vi (1≤ui,vi≤n), indicating there is a link between nodes ui and vi and the direction is from ui to vi.
∑n≤3∗105,∑m≤6∗105
1≤n,m≤105
The first line contains two integers n and m,the number of vertexs and the number of edges.Next m lines contain two integers each, ui and vi (1≤ui,vi≤n), indicating there is a link between nodes ui and vi and the direction is from ui to vi.
∑n≤3∗105,∑m≤6∗105
1≤n,m≤105
Output
For each test case,print m lines.The i-th line includes one integer:the length of edge from ui to vi
Sample Input
2
4 6
1 2
2 4
1 3
1 2
2 2
2 3
4 6
1 2
2 3
1 4
2 1
2 1
2 1
4 6
1 2
2 4
1 3
1 2
2 2
2 3
4 6
1 2
2 3
1 4
2 1
2 1
2 1
Sample Output
1
2
2
1
4
4
1
1
3
4
4
4
2
2
1
4
4
1
1
3
4
4
4
Author
SXYZ
Source
题目大意：给定一张n个点m条有向边的图，构造每条边的边权（边权为正整数），令d(x)表示1到x的最短路，使得存在点i(1<=i<=n)满足d(1)<d(2)<…<d(i)>d(i+1)>…>d(n)。
分析：有关最短路的构造题，和hdu4903有点类似，都是事先确定最短路再来构造边权.
首先，令每个点的最短路都在[0,n-1]区间内，并且每个点的最短路都不一样.如果能够能够使所有点的最短路都合理，那么对于一条边所连的点u,v，只需要这条边的权值等于abs(d(v) - d(u))即可.这就能满足最短路的要求.
接下来是要使得最短路合理.从两边向中间构造,维护两个指针l,r和一个计数器cnt,一开始l = 2,r = n.先设d[1] = 0,将1号点连边指向的点都打上标记.接着从l,r指针指向的点中选一个打上标记的点，那么这个点的d值就是++cnt.然后把这个点连边所指向的点都打上标记，并且向中间移动指针.因为题目保证有解，所以每次必然有一个指针能够移动.
这样做是使得这些点到1的最短路合理，如果直接胡乱分配d,设定边权，那么可能只是这条边是最短路上的边，但实际上这些点到1的最短路并不一定是分配好的d.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm> using namespace std; const int maxn = ; int T,n,m,head[maxn],nextt[maxn],to[maxn],tot = ,d[maxn],cnt;
bool vis[maxn]; struct node
{
int x,y,w;
}e[]; void add(int x,int y)
{
to[tot] = y;
nextt[tot] = head[x];
head[x] = tot++;
} int main()
{
scanf("%d",&T);
while (T--)
{
memset(head,,sizeof(head));
memset(vis,false,sizeof(vis));
memset(d,,sizeof(d));
cnt = ;
tot = ;
scanf("%d%d",&n,&m);
for (int i = ; i <= m; i++)
{
scanf("%d%d",&e[i].x,&e[i].y);
add(e[i].x,e[i].y);
}
d[] = ;
for (int i = head[];i;i = nextt[i])
{
int v = to[i];
vis[v] = ;
}
int l = ,r = n;
while (cnt < n)
{
int u;
if (vis[l])
u = l++;
else
u = r--;
d[u] = cnt++;
for (int i = head[u];i;i = nextt[i])
{
int v = to[i];
vis[v] = ;
}
}
for (int i = ; i <= m; i++)
{
if(e[i].x == e[i].y)
printf("%d\n",n);
else
printf("%d\n",abs(d[e[i].x] - d[e[i].y]));
}
} return ;
}