Contents
JZOJ – 5794 旅行
Time Limit : 1500ms
Memory Limit : 128MB
Description
悠悠岁月，不知不觉，距那传说中的 $ pppfish $ 晋级泡泡帝已是过 去数十年。数十年中，这颗泡泡树上，也是再度变得精彩，各种泡泡天才辈出，惊艳世人，然而，似乎 不论后人如何的出彩，在他们的头顶之上，依然是有着一道身影而立。 泡泡帝，$ pppfish $ 。 现在，$ pppfish $ 即将带着被自己收服的无数个泡泡怪前往下一个 空间，而在前往下一个空间的道路上，有 $ N $ 个中转站，和M条空间虫洞连接中转站（双向通道，可有重边，可有环），然而，通过虫洞 是要一定的条件的，pppfish将手下所有泡泡怪编号为 $ 1，2 … $ +$ ∞ $ ,对于每个空间虫洞，有两个值L和R，表示此虫洞只允许编号从 $ L $ 到 $ R $ 的泡泡怪通过，$ pppfish $ 现在在 $ 1 $ 号中转站，他想带尽可能多的泡 泡怪到达N号中转站，于是 $ pppfish $ 找到了机智的你，希望你告诉 他最多可以带多少个泡泡怪，同时他还想知道所 有泡泡怪的编号（若有多组解取字典序最小的一组)
Input
第一行两个用空格隔开的整数 $ N，M $ ($ 2\leq N \leq 1000，0 \leq M \leq 3000 $ ) 接下来 $ M $ 行，每行四个用空格隔开的整数 $ a，b，l，r $ 表示在$ a $ ，$ b $ 中转站间有一个空间虫洞允许编号 $ l~r $ 的泡泡怪通过。（$ 1 \leq a， b \leq N，1 \leq l \leq r \leq 10^6 $)
Output
第一行一个整数 $ ans $ ，表示最多能携带的泡泡怪数量 接下来一行 $ ans $ 个用空格隔开的正整数，表示泡泡怪的编号,从小到大依次输出,如果没有泡泡怪能通过只要输出 $ 0 $ 就可以了
Sample Input
Case 1
4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7
Case 2
2 2
1 2 1 3
1 2 4 6
Sample Output
Case 1
6
2 3 4 5 6 7
Case 2
3
1 2 3
Data Constraint
30%的数据 $ 1 \leq N,M \leq 10 $
100%的数据 $ 2 \leq N \leq 1000 $ , $ 0 \leq M \leq 3000, 1 \leq a, b \leq N, 1 \leq l \leq r \leq 10^6 $
解题思路
先想到一种做法，对于每一个可能的 $ l $，我们枚举得到到一个 $ r $，dfs判断图是否联通，得到答案。
然后发现 $ r $ 可以通过二分的方法枚举，降低复杂度
这样可以得到 30pts Time Limit Exceeded 的好（暴力）成绩
如果不考虑二分，那么 $ r $ 的枚举就会变成连续的，我们可以不对每一个 $ r $ 都跑一遍dfs，而是可以用并查集维护图是否联通。
我们将边存入结构体中,并copy一份，一份以 $ l $ 从小到大排序，一份以 $ r $ 从大到小排序。
还是从小到大枚举 $ l $，然后初始化并查集。在以 $ r $ 从大到小枚举边，如果一条边的允许通过的左端点 $ l’ $ 小于等于 $ l $，我们将两个点在并查集中加入一起，只到 $ 1 $ 和 $ n $ 联通。
求出 $ r-l+1 $ 作为他们的 $ length $，如果 $ length $ 比之前大（不能取等，因为字典序要最小），更新答案。
算法时间复杂度 $ O(m^2) $
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1000 + 10;
const int MAXM = 3000 + 10;
int n, m;
struct Edge{
int a, b;
int l, r;
};
Edge edge[MAXM];
Edge edge2[MAXM];
inline bool cmp(Edge x, Edge y){
return x.l < y.l;
}
inline bool cmp2(Edge x, Edge y){
return x.r > y.r;
}
inline int read(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
ch = getchar();
}
while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return x;
}
int together[MAXN];
inline int find(int x){
int root = x;
while(root != together[root]){
root = together[root];
}
while(x != root){
int tmp = together[x];
together[x] = root;
x = tmp;
}
return root;
}
inline void merge(int a, int b){
int fa = find(a);
int fb = find(b);
together[fa] = fb;
}
int main(){
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
n = read();
m = read();
for(register int i=0; i<m; i++){
edge[i].a = read();
edge[i].b = read();
edge[i].l = read();
edge[i].r = read();
edge2[i] = edge[i];
}
sort(edge, edge+m, cmp);
sort(edge2, edge2+m, cmp2);
int ans = 0;
int al = 0, ar = 0;
for(register int i=0; i<m; i++){
int left = edge[i].l;
for(register int j=1; j<=n; j++){
together[j] = j;
}
int right = -1;
for(register int j=0; j<m; j++){
if(edge2[j].l <= left){
merge(edge2[j].a, edge2[j].b);
}
if(find(1) == find(n)){
right = edge2[j].r;
break;
}
}
int length = 0;
if(right != -1){
length = right - left + 1;
}
if(length > ans){
ans = length;
al = left;
ar = right;
}
}
printf("%d\n", ans);
for(register int i = al; i<= ar; i++){
printf("%d ", i);
}
}