题目地址：HDUOJ：Problem – 5385

题目描述

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.
给你一个有向图，你要确定每条边的边权，使得存在1到每个点的最短路距离d满足d(1)<d(2)<….d(x)>d(x+1)>…d(n)。

输入输出格式

输入格式：
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∗10^5,∑m≤6∗10^5
1≤n,m≤10^5

输出格式：
For each test case,print m lines.The i-th line includes one integer:the length of edge from ui to vi

输入输出样例

输入样例#1：

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

输出样例#1：

1
2
2
1
4
4
1
1
3
4
4
4

题解

其实这道题如果能想到Prim算法的流程就好做了。Prim是确定一个点的d为0，然后向外扩展到当前选定点集距离最小的点，扩展完毕以后就是一棵最短路树/最小生成树。那么我们也来构造这样一棵最短路树/最小生成树，使得树边满足题目要求且非树边边权极大就可以了。
我们确定1为树根，d(1)=0，然后从最小号点和最大号点开始往里加点，每加一个点就给它的出边和相邻点打标记，表示这些边/点以后应当计算。
虽然数据范围长得很像O(n \log n)，但其实算法是O(m)的。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 600005;

struct Edge {
    int u, v, id;
};

int T, n, m, ut, vt, dis[MAXN];
std::vector<Edge> gra[MAXN], edges;
bool vis[MAXN], ans[MAXN];

inline void work(int u, int d) {
    dis[u] = d;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].v;
        if(vis[v]) continue;
        vis[v] = true;
        ans[gra[u][i].id] = true;
    }
}

int main() {
    T = readint();
    while(T--) {
        n = readint(); m = readint();
        memset(dis, 0, sizeof(dis));
        memset(ans, 0, sizeof(ans));
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++) gra[i].clear();
        edges.clear();
        for(int i = 1; i <= m; i++) {
            ut = readint(); vt = readint();
            gra[ut].push_back(Edge {ut, vt, i});
            edges.push_back(Edge {ut, vt, i});
        }
        int l = 1, r = n, d = 0;
        vis[l] = true;
        while(l <= r) {
            if(vis[l]) work(l++, d++);
            if(vis[r]) work(r--, d++);
        }
        for(int i = 1; i <= m; i++) {
            if(ans[i]) {
                printf("%d\n", std::abs(dis[edges[i - 1].u] - dis[edges[i - 1].v]));
            } else {
                printf("%d\n", n);
            }
        }
    }
    return 0;
}