CF366D Dima and Trap Graph
在一张无向图上有 N N N 个点和 M M M 条边，每条边连接着点 a a a 和点 b b b，有无数个人编号为 1 , 2 , … , + ∞ 1,2,dots,+infty 1,2,…,+∞。通过某条边是要一定的条件的，对于每条边，有两个值 l l l 和 r r r，表示该条边只允许编号在 [ l , r ] [l,r] [l,r] 区间内的人通过，从 1 1 1 号点到达 N N N 号点，请求出最多有多少人可以通过，并求出这些人的编号（若有多组解取字典序最小的一组 )
- 可能有重边和自环。
- 如果没有人能通过只要输出 Nice work, Dima! 就可以了。
- 对于 30 % 30% 30% 的数据， 1 ≤ N , M ≤ 10 1le N,Mle10 1≤N,M≤10；
- 对于 100 % 100% 100% 的数据， 2 ≤ N ≤ 1000 , 0 ≤ M ≤ 3000 , 1 ≤ a , b ≤ N , 1 ≤ l ≤ r ≤ 1 0 6 2le Nle1000,0le Mle3000,1le a,ble N,1le lle rle10^6 2≤N≤1000,0≤M≤3000,1≤a,b≤N,1≤l≤r≤106。
有两种思路（注意字典序最小的判断）：
1. 1. 1. 最长路遍历每一条边，对于第 i i i 条边，选取边权 ≥ l i ge l_i ≥li 的边，从 1 1 1 到 N N N 跑最长路，让 r r r 最大，在 l l l 固定的情况下，肯定是 r r r 越大越好。
时间复杂度 O ( M ⋅ M log N ) = O ( M 2 log N ) mathcal{O}(Mcdot Mlog N)=mathcal{O}(M^2log N) O(M⋅MlogN)=O(M2logN)。
2. 2. 2. 并查集同样是遍历每一条边 i i i，将所有满足 l j ≤ l i l_jle l_i lj≤li 的 j j j，都把 a j a_j aj 和 b j b_j bj 并入一个集合。
那么最终的 l l l 一定是 l i l_i li，所以把所有的 r i r_i ri 取个 min min min 作为最终的 r r r，当点 1 1 1 和点 N N N 在同一个集合内说明可以尝试去更新答案。
因为是并查集实现，结合路径压缩和按秩合并可以做到 O ( M 2 α ( N ) ) mathcal{O}(M^2alpha(N)) O(M2α(N))，不过因为 N ≤ 1000 Nle1000 N≤1000 所以优化不大，主要优化在于常数（
时间复杂度 O ( M 2 α ( N ) ) mathcal{O}(M^2alpha(N)) O(M2α(N))。
Code text{Code} Code 1. 1. 1.#include2. 2. 2.#include #include #include using namespace std; const int MAXN = 1005; const int MAXM = 3005; const int INF = 0x3f3f3f3f; int cnt; int head[MAXN]; struct edge { int to, l, r, nxt; }e[MAXM << 1]; void add(int u, int v, int l, int r) { e[++cnt] = edge{v, l, r, head[u]}; head[u] = cnt; } int dis[MAXN]; bool vis[MAXN]; struct node { int u, r; bool operator <(const node &x)const { if (x.r == r) { return x.u < u; } return x.r > r; } }; void init() { memset(dis, -INF, sizeof(dis)); memset(vis, false, sizeof(vis)); } void dijkstra(int l) { init(); dis[1] = INF; priority_queue pq; pq.push(node{1, dis[1]}); while (!pq.empty()) { int u = pq.top().u; pq.pop(); if (vis[u]) { continue; } vis[u] = true; for (int i = head[u]; i; i = e[i].nxt) { if (e[i].l > l) //取在区间内的 { continue; } int v = e[i].to; if (dis[v] < min(dis[u], e[i].r)) //r要取min { dis[v] = min(dis[u], e[i].r); pq.push(node{v, dis[v]}); } } } } int l[MAXM], r[MAXM]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d%d%d", &u, &v, l + i, r + i); add(u, v, l[i], r[i]); add(v, u, l[i], r[i]); } int ansk = 0, ansl = 0, ansr = 0; for (int i = 1; i <= m; i++) { dijkstra(l[i]); int res = dis[n] - l[i] + 1; if (ansk < res || (ansk == res && ansl > l[i])) { ansk = res; ansl = l[i]; ansr = dis[n]; } } if (ansk) { printf("%dn", ansk); for (int i = ansl; i <= ansr; i++) { printf("%d ", i); } } else { puts("Nice work, Dima!"); } return 0; }
#include#include #include using namespace std; const int MAXN = 1005; const int MAXM = 3005; const int INF = 0x3f3f3f3f; struct edge { int u, v, l, r; }e[MAXM]; bool cmp(edge x, edge y) { if (x.r == y.r) { return x.l < y.l; } return x.r > y.r; } int n, m, r, ansk, ansl, ansr; int fa[MAXN], siz[MAXN]; void init() { for (int i = 1; i <= n; i++) { fa[i] = i; siz[i] = 1; } } int find(int x) { if (x == fa[x]) { return x; } return fa[x] = find(fa[x]); //路径压缩 } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].l, &e[i].r); } sort(e + 1, e + m + 1, cmp); for (int i = 1; i <= m; i++) { init(); r = INF; for (int j = 1; j <= m; j++) { if (e[j].l <= e[i].l) { int x = find(e[j].u), y = find(e[j].v); if (x != y) { if (siz[x] > siz[y]) //按秩合并 { fa[y] = x; siz[x] += siz[y]; } else { fa[x] = y; siz[y] += siz[x]; } r = min(r, e[j].r); if (find(1) == find(n)) { break; } } } } if (find(1) == find(n) && (ansk < r - e[i].l + 1 || (ansk == r - e[i].l + 1 && ansl > e[i].l))) { ansk = r - e[i].l + 1; ansl = e[i].l; ansr = r; } } if (ansk) { printf("%dn", ansk); for (int i = ansl; i <= ansr; i++) { printf("%d ", i); } } else { puts("0"); } return 0; }
