题解
- 考虑先对所有r端从小到大排序
- 然后,每次枚举一个r端
- 然后将所有大于r坐标的路径打入并差集
- 然后判断1和n是否在同一个并差集里
- 如果是,则判断r[i]-e[j].l+1是否大于当前ans,更新答案
- 记录ans的左端点和长度
- 以便输出泡泡怪的编号
代码
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 #include <cmath>
5 #include <cstring>
6 using namespace std;
7 struct edge { int a,b,l,r; }e[3010];
8 int n,m,r[3010],fa[3010],num,mxl;
9 bool cmp(edge x,edge y) { return x.l<y.l; }
10 int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
11 int main()
12 {
13 scanf("%d%d",&n,&m);
14 for (int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].a,&e[i].b,&e[i].l,&e[i].r),r[i]=e[i].r;
15 sort(r+1,r+m+1);
16 sort(e+1,e+m+1,cmp);
17 for (int i=1;i<=m;i++)
18 {
19 for (int j=1;j<=n;j++) fa[j]=j;
20 for (int j=1;j<=m;j++)
21 if (e[j].r>=r[i])
22 {
23 int x=find(e[j].a),y=find(e[j].b);
24 if (x!=y) fa[x]=y;
25 if (find(1)==find(n)) if (r[i]-e[j].l+1>num) num=r[i]-e[j].l+1,mxl=e[j].l;
26 }
27 }
28 printf("%d
",num);
29 for (int i=mxl;i<=mxl+num-1;i++) printf("%d ",i);
30 return 0;
31 }