1 /*
2 题意：给一张图和一些有向边，问如何给边赋值使得d1 < d2 < .. < dx > ,,,< ddn
3 贪心：左边从2开始，右边从n开始，每次选择未标记且相连的点加入树，加入时间就是d[i]，若不在树上的输出n，注意重边和重点
4 */
5 /************************************************
6 * Author :Running_Time
7 * Created Time :2015-8-13 12:09:17
8 * File Name :F.cpp
9 ************************************************/
10
11 #include <cstdio>
12 #include <algorithm>
13 #include <iostream>
14 #include <sstream>
15 #include <cstring>
16 #include <cmath>
17 #include <string>
18 #include <vector>
19 #include <queue>
20 #include <deque>
21 #include <stack>
22 #include <list>
23 #include <map>
24 #include <set>
25 #include <bitset>
26 #include <cstdlib>
27 #include <ctime>
28 using namespace std;
29
30 #define lson l, mid, rt << 1
31 #define rson mid + 1, r, rt << 1 | 1
32 typedef long long ll;
33 const int MAXN = 3e5 + 10;
34 const int MAXM = 6e5 + 10;
35 const int INF = 0x3f3f3f3f;
36 const int MOD = 1e9 + 7;
37 vector<int> G[MAXN];
38 bool vis[MAXN];
39 int fa[MAXN];
40 int d[MAXN];
41 int u[MAXN], v[MAXN];
42 int n, m;
43
44 void mark(int u) {
45 for (int i=0; i<G[u].size (); ++i) {
46 int v = G[u][i];
47 if (fa[v] || vis[v]) continue;
48 fa[v] = u;
49 }
50 }
51
52 void work(void) {
53 memset (d, 0, sizeof (d));
54 memset (fa, 0, sizeof (fa));
55 memset (vis, false, sizeof (vis));
56 int l = 2, r = n, now = 0;
57 fa[1] = 0; vis[1] = true; mark (1);
58 while (l <= r) {
59 if (fa[l]) {
60 mark (l); vis[l] = true;
61 d[l] = ++now; l++; continue;
62 }
63 if (fa[r]) {
64 mark (r); vis[r] = true;
65 d[r] = ++now; r--;
66 }
67 }
68
69 for (int i=1; i<=m; ++i) {
70 if (fa[v[i]] != u[i]) printf ("%d
", n);
71 else printf ("%d
", abs (d[u[i]] - d[v[i]]));
72 }
73 }
74
75 int main(void) { //HDOJ 5385 The Path
76 int T; scanf ("%d", &T);
77 while (T--) {
78 scanf ("%d%d", &n, &m);
79 for (int i=1; i<=n; ++i) G[i].clear ();
80 for (int i=1; i<=m; ++i) {
81 scanf ("%d%d", &u[i], &v[i]);
82 G[u[i]].push_back (v[i]);
83 }
84 work ();
85 }
86
87 return 0;
88 }
贪心 HDOJ 5385 The Path
编译人生，运行世界！