# [题解] JZOJ – 5794 旅行

## JZOJ – 5794 旅行

Time Limit : 1500ms
Memory Limit : 128MB

## 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$

## 代码

#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;
}

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);

for(register int i=0; i<m; i++){

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);
}
}