[ZJOJ] 5794 2018.08.10【2018提高组】模拟A组&省选旅行

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<=1e6

Output

第一行一个整数ans，表示最多能携带的泡泡怪数量接下来一行ans个用空格隔开的正整数，表示泡泡怪的编号,从小到大依次输出,如果没有泡泡怪能通过只要输出“0”就可以了

Sample Input

Sample Output

Output1:
6
2 3 4 5 6 7 
Output2:
3
1 2 3

Data Constraint

30%的数据 1 <= N,M <= 10
100%的数据 2 <= N <= 1000, 0 <= M <= 3000, 1 <= a, b <= N, 1 <= l <= r <= 10^6

题目解析

数据范围不算大，看了看题首先可以得出一个推论：答案区间一定是连续的。

所以我们只要知道区间的左右段就可以了，枚举一下就很好做了。

用并查集 + 贪心的思想，将所有边按右端点的限制大小排序，之后贪心的合并点，同时选取边，当点1和点n在同一集合内，就结束枚举，过程中记录答案。

其实有点像Kruskal的过程。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

//1<=a , b<=N , 1<=l<=r<=1e6
const int MAXN = 1005;
const int MAXM = 3005;

int n,m;
int ans,cnt,lft;
int fa[MAXN];
struct Edge {
    int from,to;
    int L,R;
} l[MAXM << 1];

bool cmp(Edge x,Edge y) {
    return x.R > y.R;
}

int _find(int x) {
    if(x == fa[x]) return x;
    return fa[x] = _find(fa[x]);
}

int _min(int x,int y) {
    return x < y ? x : y;
}

int _max(int x,int y) {
    return x > y ? x : y;
}

inline void add(int x,int y,int a,int b) {
    cnt++;
    l[cnt].from = x;
    l[cnt].to = y;
    l[cnt].L = a;
    l[cnt].R = b;
    return;
}

inline void init_fa() {
    for(int i = 1;i <= n;i++) fa[i] = i;
    return;
}

inline void Dinic(int s,int t) {
    for(int i = 1;i <= m;i++) {
        init_fa();
        for(int j = 1;j <= m;j++) {
            if(l[j].L > l[i].L) continue;
            fa[_find(l[j].from)] = _find(l[j].to);
            if (_find(1)==_find(n)) {
                if(l[j].R - l[i].L > ans - 1) {
                    lft = l[i].L;
                    ans = l[j].R - l[i].L + 1;
                }
                break;
            }
        }
    }
    return;
}

int main() {
    scanf("%d%d",&n,&m);
    int x,y,a,b;
    for(int i = 1;i <= m;i++) {
        scanf("%d%d%d%d",&x,&y,&a,&b);
        add(x,y,a,b);
    }
    for(int i = 1;i <= n;i++ ){
        fa[x] = x;
    }
    sort(l+1,l+1+m,cmp);
    Dinic(1,n);
    printf("%d
",ans);
    for(int i = lft;i<=lft + ans - 1;i++) {
        printf("%d ",i);
    }
    return 0;
}