[题解] JZOJ – 5794 旅行

Wong, LimstashOI, 并查集, 贪心

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≤N≤1000，0≤M≤3000 ) 接下来 M 行，每行四个用空格隔开的整数 a，b，l，r 表示在a ，b 中转站间有一个空间虫洞允许编号 l r 的泡泡怪通过。（1≤a，b≤N，1≤l≤r≤106)

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
C++

Case 2

2 2
1 2 1 3
1 2 4 6
C++

Sample Output

Case 1

6
2 3 4 5 6 7
C++

Case 2

3
1 2 3
C++

Data Constraint

30%的数据 1≤N,M≤10
100%的数据 2≤N≤1000 , 0≤M≤3000,1≤a,b≤N,1≤l≤r≤106

解题思路

先想到一种做法，对于每一个可能的 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(m2)

代码

#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);
    }
}
C++